链表

链表相关的核心点

NULL 异常处理dummy node(哑巴节点)快慢指针插入一个节点到排序链表从一个链表中移除一个节点翻转链表合并两个链表找到链表的中间节点

哑巴节点

​ 哑节点（dummy node）是初始值为NULL的节点，创建在使用到链表的函数中，可以起到避免处理头节点为空的边界问题的作用，减少代码执行异常的可能性。也就是说，哑节点的使用可以对代码起到简化作用（省略当函数的入口参数为空时的判断）。

// 普通结构体 struct ListNode { int val; struct ListNode *next; }; // 定义函数 ListNode *addNode( ListNode *node, int num){ // 函数返回的是尾节点 struct ListNode *new = (struct ListNode*) malloc(sizeof(struct ListNode) * num); node->next = new; return new; } // 问题是当node节点为空时，便会产生异常，node->next = new会报错，应该修改如下 ListNode *addNode( ListNode *node, int num){ // 函数返回的是尾节点 struct ListNode *new = (struct ListNode*) malloc( sizeof(struct ListNode) * num ); if( null == node ){ // 头节点为空的情况 return new; // 直接返回新建的节点（头节点的地址），相当于新建了一组链表 } node->next = new; return new; } // 定义哑节点如下 struct ListNode *dummyNode= (struct ListNode*) malloc(sizeof(struct ListNode)); dummyNode->val = NULL; dummyNode->next = NULL; // 函数addNode()重新定义如下 ListNode *addNode( ListNode *dummyNode, int num) // 函数返回的是尾节点 struct ListNode *new = (struct ListNode*) malloc( sizeof(struct ListNode) * num ); /* 此处不再需要处理头节点为空的情况，因为dummyNode一定非空 */ dummyNode->next = new; return new; }

快慢指针

​ 快慢指针就是定义两根指针，移动的速度一快一慢，以此来制造出自己想要的差值。这个差值可以让我们找到链表上相应的节点。比如，我们把一个链表看成一个跑道，假设a的速度是b的两倍，那么当a跑完全程后，b刚好跑一半，以此来达到找到中间节点的目的。

常见题型

删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ // 递归 class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL) { return head; } if(head->next){ head->next = deleteDuplicates(head->next); if(head->val == head->next->val) { head = head->next; // 删除head } } return head; } }; // 迭代 class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* current = head; while(current) { while(current->next && current->val == current->next->val) { current->next = current->next->next; } current = current->next; } return head; } };

删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。

思路：链表头结点可能被删除，所以用dummy node辅助删除

// 递归 class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL) return head; if(head->next && head->val == head->next->val) { while(head->next && head->val == head->next->val) { head = head->next; } return deleteDuplicates(head->next); } else { head->next = deleteDuplicates(head->next); } return head; } }; // 迭代 class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL) { return head; } // 链表头结点可能被删除，所以用dummy node辅助删除 struct ListNode *dummyNode= (struct ListNode*) malloc(sizeof(struct ListNode)); dummyNode->next = head; head = dummyNode; // 之后不管head怎么移动，dummyNode->next就是head移动完的链表的头结点 int temp; while(head->next && head->next->next) { if(head->next->val == head->next->next->val) { temp = head->next->val; while(head->next && head->next->val == temp) { head->next = head->next->next; } } else { head = head->next; } } return dummyNode->next; } };

注意点 ◉ A->B->C 删除 B，A->next = C ◉ 删除用一个dummy node节点辅助（允许头节点可变） ◉ 访问 X->next 、X->value 一定要保证 X != NULL

反转链表

反转一个单链表。

思路：用一个prev节点保存向前指针，next保存向后的临时指针

// 递归，参考https://leetcode-cn.com/problems/reverse-linked-list/solution/zhu-bu-tu-jie-di-gui-die-dai-by-sucongcjs/ class Solution { public: ListNode* reverseList(ListNode* head) { if (head == NULL || head->next == NULL) { return head; } ListNode* ret = reverseList(head->next); head->next->next = head; head->next = NULL; return ret; } }; // 迭代 class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *next = NULL; ListNode *prev = NULL; while(head) { /** * 保存当前head->next节点，防止重新赋值后被覆盖 * 一轮之后状态：NULL <- 1 2 -> 3 -> 4 * prev head */ next = head->next; head->next = prev; prev = head; // prev 移动 head = next; // head 移动 } return prev; } };

反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

思路：先遍历到 m 处，翻转，再拼接后续，注意指针处理

// 递归，参考https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/bu-bu-chai-jie-ru-he-di-gui-di-fan-zhuan-lian-biao/ class Solution { public: ListNode* successor = NULL; // 后驱节点 // 反转以 head 为起点的 n 个节点，返回新的头结点 ListNode* reverseN(ListNode* head, int n) { if (n == 1) { // 记录第 n + 1 个节点 successor = head->next; return head; } // 以 head.next 为起点，需要反转前 n - 1 个节点 ListNode* last = reverseN(head->next, n - 1); head->next->next = head; // 让反转之后的 head 节点和后面的节点连起来 head->next = successor; return last; } ListNode* reverseBetween(ListNode* head, int m, int n) { // base case if (m == 1) { return reverseN(head, n); } // 前进到反转的起点触发 base case head->next = reverseBetween(head->next, m - 1, n - 1); return head; } }; // 迭代 class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { // 思路：先遍历到m处，翻转，再拼接后续，注意指针处理 // 输入: 1->2->3->4->5->NULL, m = 2, n = 4 if (head == NULL) { return head; } // 头部变化所以使用dummy node ListNode* dummyNode = (struct ListNode*)malloc(sizeof(struct ListNode)); dummyNode->next = head; head = dummyNode; // 最开始：0->1->2->3->4->5->NULL ListNode* pre = NULL; int i = 0; while (i < m) { pre = head; head = head->next; i++; } // 遍历之后： 1(pre)->2(head)->3->4->5->NULL // i = 1 int j = i; ListNode* next = NULL; ListNode* mid = head; // 用于中间节点连接 while (head != NULL && j <= n) { // 第一次循环： 1(pre) NULL<-2 3(head)->4->5->NULL ListNode* temp = head->next; head->next = next; next = head; head = temp; j++; } // 循环需要执行四次 // 循环结束：1(pre) NULL<-2<-3<-4 5(head)->NULL pre->next = next; mid->next = head; return dummyNode->next; } };

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

思路：通过 dummy node 链表，连接各个元素

// 递归 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == nullptr) { return l2; } else if (l2 == nullptr) { return l1; } else if (l1->val < l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } } }; // 迭代 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (l1 == NULL) { return l2; } else if (l2 == NULL) { return l1; } // 头部变化所以使用dummy node ListNode* dummyNode = (struct ListNode*)malloc(sizeof(struct ListNode)); ListNode* head = dummyNode; while (l1 != NULL && l2 != NULL) { if (l1->val < l2->val) { head->next = l1; l1 = l1->next; } else { head->next = l2; l2 = l2->next; } head = head->next; } while (l1 != NULL) { head->next = l1; head = head->next; l1 = l1->next; } while (l2 != NULL) { head->next = l2; head = head->next; l2 = l2->next; } return dummyNode->next; } };

分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

思路：将大于 x 的节点，放到另外一个链表，最后连接这两个链表

// 迭代 class Solution { public: ListNode* partition(ListNode* head, int x) { if (head == NULL) { return head; } ListNode* headDummy = (struct ListNode*)malloc(sizeof(struct ListNode)); headDummy->next = head; head = headDummy; ListNode* tailDummy = (struct ListNode*)malloc(sizeof(struct ListNode)); ListNode* tail = tailDummy; while (head->next) { if (head->next->val < x) { head = head->next; } else { ListNode* temp = head->next; head->next = head->next->next; tail->next = temp; tail = tail->next; } } tail->next = NULL; head->next = tailDummy->next; return headDummy->next; } };