链表理论基础

• 链表是一种通过指针串连在一起的线性结构，每一个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针）。最后一个节点的指针指向 null。
• 链表的存储方式：数组在内存中是连续存储的，但链表不是连续存储的，各个节点分布在内存的不同地址空间中，用指针串联在一起。
• 链表的定义：

// 单链表
struct ListNode{int val;  // 节点上存储的值ListNode *next;  // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {}  // 链表节点的构造函数
};

C++ 也默认生成了一个构造函数，但这个构造函数不会初始化任何成员变量：
我们自己的构造函数初始化链表节点：ListNode* head = new ListNode(5);
使用默认的构造函数初始化：ListNode* head = new ListNode(); head->val = 5;

• 删除或增加节点：这个操作与其他节点是无关的，时间复杂度为 O(1)。但是在指定位置操作，还需要有查询操作。另外注意删除节点时只是改变指针指向，删除的节点仍在内存中，最好去主动释放。
• 查找：链表只能从一端开始遍历，因此时间复杂度为 O(n)。
• 性能分析：数组固定长度，连续存储，在删除或插入元素时，需要逐个移动元素，时间复杂度 O(n)，但查找方便，时间复杂度 O(1)。链表长度并不固定，不连续存储，增删元素时间复杂度为 O(1)，但查找 O(n)。
  因此数组适用于数据量固定，查找频繁，较少增删；链表适用于数据量不固定，增删频繁，较少查找的情景。

移除链表元素

之前我们做过一道移除链表元素的题，其难点在于数组连续存储，所以移除元素之后还需要移动其他元素保证连续。但是链表不需要保证连续存储，移除操作与其他元素无关的，其实我们直接遍历整条链表就可以了。
处理过程需要注意的问题：头节点与其他节点不同的处理办法。其他节点都是改变前一个节点的指针指向，但删除头节点的话需要不断向后更新头节点。可以添加一个虚拟节点 dummy 使得头节点的处理一般化。

class Solution{
public:ListNode* removeElements(ListNode* head, int val){ListNode* dummy = new ListNode();dummy->next = head;ListNode* cur = dummy;while(cur->next != NULL){  // 用cur->next进行判断，注意删除节点释放内存的操作if(cur->next->val == val){ListNode* tmp = cur->next;cur->next = cur->next->next;delete tmp;}else  cur = cur->next;}head = dummy->next;delete dummy;return head;}
};

设计链表

注意C++语法。public 和 private 的前后顺序。维护一个虚拟节点和节点数目会使其他操作更加方便。

class MyLinkedList{
public:struct ListNode{int val;ListNode* next;ListNode(int val) : val(val), next(NULL) {}};MyLinkedList(){_dummyHead = new ListNode(0);_size = 0;}int get(int index){if(index < 0 || index > _size - 1)  return -1;ListNode* cur = _dummyHead->next;while(index--){cur = cur->next;}return cur->val;}void addAtHead(int val){ListNode* node = new ListNode(val);ListNode* cur = _dummyHead;node->next = _dummyHead->next;_dummyHead->next = node;_size++;}void addAtTail(int val){ListNode* node = new ListNode(val);ListNode* cur = _dummyHead;while(cur->next){cur = cur->next;}cur->next = node;_size++;}void addAtIndex(int index, int val){if(index < 0 || index > _size)  return;ListNode* node = new ListNode(val);ListNode* cur = _dummyHead;while(index--){cur = cur->next;}node->next = cur->next;cur->next = node;_size++;}void deleteAtIndex(int index){if(index < 0 || index > _size - 1)  return;ListNode* cur = _dummyHead;while(index--){cur = cur->next;}cur->next = cur->next->next;_size--;}
private:int _size;  // 记录链表中的节点数目ListNode* _dummyHead;  // 设计一个虚拟节点，解决头节点的问题
};

反转链表

链表只能头节点开始遍历，为了避免新建链表，可以选择使用双指针法。一个指针指向前一个节点，一个指针指向当前节点。注意：在遍历过程中会改变 next 指针的指向，所以要使用中间变量来记录下一个节点，再改变当前节点的 next 指针指向。

class Solution{
public:ListNode* reverseList(ListNode* head){if(!head)  return head;ListNode* cur = head;ListNode* pre = NULL;while(cur){ListNode* tmp = cur->next;  // 记录当前节点的下一个cur->next = pre;  // 翻转当前节点的指向pre = cur;  // 向后遍历cur = tmp;}return pre;}
};

递归法，上面的迭代法可以改写成递归。

class Solution{
public:ListNode* reverse(ListNode* pre, ListNode* cur){if(!cur)  return pre;ListNode* tmp = cur->next;cur->next = pre;return reverse(cur, tmp);}ListNode* reverseList(ListNode* head){return reverse(NULL, head);}
};

还有另一种比较难以想到的方法，是从后往前翻转。

class Solution{
public:ListNode* reverseList(ListNode* head){if(head == NULL)  return head;if(head->next == NULL)  return head;ListNode* last = reverseList(head->next);  // 把原链表末尾的节点返回（翻转后的头节点）head->next->next = head;  // 将head节点移到队列尾部，注意这一步没有改变原链表中指向head的指针，使得每层递归都能将当前head移动到队尾head->next = NULL;  // head移到队尾，指向空节点return last;}
};