ch2

lc707
主要在链表类中， 实现以下成员函数：

• get(index)：获取链表中第 index 个节点的值。
  

  
  

  如果索引无效，则返回-1。
  

  
  

• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。
  

  
  

  插入后，新节点将成为链表的第一个节点。
  

  
  

• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  

  
  

• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。
  

  
  

  如果 index 等于链表的长度，则该节点将附加到链表的末尾。
  

  
  

  如果 index 大于链表长度，则不会插入节点。
  

  
  

  如果-- index小于0，则在头部插入节点。
  

  
  

• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
  

  
  

1 设计链表 1.0 下划线命名

系统头文件里将宏名、变量名、内部函数名用 _ 开头就是为了避免与用户用的名字冲突。

因为当＃include 系统头文件时，这些文件里的名字都有了定义，如果与你用的名字冲突，就可能引起各种奇怪现象。

换句话说：通常情况下程序时不要用 _ 开头的名字，以免与系统头文件的名字冲突。

C++ 中一种使用下划线开头的变量 情况：
通常是表示是类的私有成员变量。

结构体， 类 {} 后面有分号；
成员函数后面 没有分号；

1.1 构造函数的两种写法

1. 列表的方式，构造函数；

2. 在函数中，给成员变量赋值；

注意， 当构造函数中， 带有指针成员变量时：
使用列表的方式 定义 构造函数；

    struct ListNode {
        int val;  // 节点中保存的数值
        ListNode *next;  // 节点中指向下一个节点的指针；

        // 注意区别构造函数 与默认构造函数  构造函数名称与类名称相同， 而默认构造函数， 没有形参；
        // 此处， 定义节点的构造函数；
       ListNode(int x): val(x), next(nullptr){}
    };

1.2 虚拟头节点

变量总是先定义，后使用.
注意虚拟节点，不算做链表的计数中；
虚拟节点的设置， 是为了方便原始链表中， 对于头节点的删除， 和在头节点处增加节点；

虚拟节点的后一个节点才算做链表的头节点：
作为 index 0 开始， 代表链表的真正头节点（非虚拟节点）；

1.2 节点的起始位置

注意这里有个关键点，

就是当前节点 是从虚拟节点 开始， 还是从 头节点开始；
这会影响到 index 最终所在的位置！

假设链表有四个节点， 那么对应的index 下标为， 0（头节点），1,2,3；
那么要获取  index = 3 位置上的数时：

如果 当前节点 是从 头节点开始：
ListNode* curNode = _dummyHead->next;
while(index--)

index 一共取了 3,2,1 这三个数，  0时不执行循环体，退出循环；
也就是循环体共执行了三次，
从而当前节点到达的位置， 正好是index 所在的位置节点；

但是， 如果当前节点是从 虚拟节点开始的:

ListNode* curNode = _dummyHead;
while(index--)

循环体共执行的次数不变，  但是由于 当前节点 是从 虚拟节点开始的，
看做从index = -1 开始的， 
所以当前节点最终到达的位置是index 的前一个位置；

class MyLinkList{

public:
    struct ListNode{
        int val;
        ListNode* next;  // 节点中保存的地址， 该地址是一个指针， 指向下一个节点；

        // 节点的构造函数，  对象初始化时会调用；
        ListNode(int x): val(x),  next(nullptr){}
    };

private:
    int _size;
    ListNode* _dummyHead;

public:
    // 自己定义类的默认构造函数， 默认构造函数，没有形参列表； 初始化链表，
    MyLinkList(){
        _dummyHead = new ListNode(0);  // 初始化头节点， 并赋值；
        _size = 0;
    }

   //  使用index 作为总共需要移动的步数， 当index 每走一步， index的数值减少1， 变为0 时， 到达index 的位置；
   //  index   从0 开始， 虚拟节点不算， 从链表的头节点开始；
   int getValue(int index){
       if (index < 0 || index > _size -1 ){ return  -1;}

       ListNode* curNode = _dummyHead->next;  // 当前节点从 头节点开始；
       while( index-- ){  //  index变为0 时，循环不运行，直接返回当前节点的数值； 当index 没有变为0 时， 说明没有到达位置处；
           curNode = curNode->next;
       }

       return  curNode->val;




    }



};

1.3 code

完整功能代码

#include
#include "vector"

using namespace std;

class MyLinkedList{
public:
    struct ListNode {
        int val;  // 节点中保存的数值
        ListNode *next;  // 节点中指向下一个节点的指针；

        // 注意区别构造函数与默认构造函数;  构造函数名称与类名称相同， 而默认构造函数， 没有形参；
        // 此处， 定义节点的构造函数；
       ListNode(int x): val(x), next(nullptr){}
    };


    // 声明私有成员变量；
private:
    int _size;
    ListNode* _dummyHead;  //  声明虚拟节点


public:
    // 定义链表类的默认构造函数（无形参）
    MyLinkedList(){
        _size = 0;
        _dummyHead = new ListNode(0);
    }


    int get(int index){
        if (index < 0 || index > _size -1){return  -1;}

        // 虚拟节点的下一个节点 为头节点；
        // 当前节点从头节点开始；
        ListNode*  curNode = _dummyHead->next;
        while(index--){ // index = 0 时，表明到达目标节点位置，退出循环，不执行循环体 ；
            curNode = curNode->next;
        }
        return curNode->val;
    }


    void addAtHead(int val){

        // 新建一个增加节点；
        ListNode* addNode = new ListNode(val);

        addNode->next = _dummyHead->next;    // 增加节点的后一个节点 赋值为原始的链表的头节点
        _dummyHead->next = addNode;  // 将虚拟节点的后一个节点 赋值为增加节点，  从而头节点变成了 增加节点；
          // 注意增加节点后， 尺寸加一；
        _size++;
    }


    void addAtTail(int val){
        ListNode* addNode = new ListNode(val);
        ListNode* curNode = _dummyHead; // 注意这里从虚拟节点开始；

        while (curNode->next != nullptr){
            curNode = curNode->next;
        }
        curNode->next = addNode;
        _size++;
    }


    void addAtIndex(int index, int val){

        if (index > _size ) return ;

        ListNode* addNode = new  ListNode(val);
        ListNode* curNode = _dummyHead;  // 当前节点从头节点开始；

        while(index--){
            curNode = curNode->next;
        }
        // index = 0 时，表明到达了 在该节点之前插入 节点， 这里称为动手节点：
        // 在该节点之前插入节点；
        addNode->next = curNode->next; //  将增加节点的后一个指针 赋值为 原始动手节点的后一个节点；
        curNode->next = addNode;
        _size++;
    }


    void deleteAtIndex(int index){
        if (index < 0 || index > _size -1) return;

        ListNode* curNode = _dummyHead;
        ListNode* tmpNode ;

        while (index--){
            curNode = curNode->next;
        }
        // 注意此时， 到达的是待删除节点的前一个节点；

        tmpNode = curNode->next;
        curNode->next = curNode->next->next;  //  将删除节点的 前一个节点中的指针赋值 删除节点的后一个节点；
        delete tmpNode;
        _size--;

    }

    void printLinkList(){
        ListNode* curNode = _dummyHead->next;
        while (curNode != nullptr){
            cout<< curNode->val << " ";
            curNode = curNode->next;
        }

    }



};

2. 反转链表

lc206
解题的关键点，

使用三个 链表节点指针， pre, cur， tmp ;

1. pre 当前节点的前一个节点， 开始赋值为空指针， 因为这将作为链表反转后 最后节点的指针指向；

2. cur 作为当前节点， 起始赋值头节点， 并且接在pre 节点的后面，

3. tmp： 当前节点的后一个节点；

4. 开始轮流依次移动 pre, cur 指针， 并且在移动过程中， 将 cur->next 调转指向， 指向pre 节点；

2.1 code

struct ListNode{
    int  val;
    ListNode* next;

    // 定义节点构造函数
    ListNode(int x): val(x), next(nullptr){}

};

class Solution{
public:

    ListNode* reverseList(ListNode* head){
        ListNode* preNode =  nullptr;  //  注意到，这里指针可以赋值为空指针；
        ListNode* curNode =  head;
        ListNode* tmpNode ;  // 保存为当前节点的后一个节点

        // 当前节点不是空指针时， 移动两个指针， 并调转curNode 中的 指针指向；
        while(curNode != nullptr){
         tmpNode = curNode->next;
         curNode->next = preNode;

         preNode = curNode;
         curNode = tmpNode;

        }
        return preNode;
        
    }
    
};