做题要点

画图

加入虚拟头节点（删除节点的时候）

auto dummy = new ListNode(-1);
dummy->next = head;

以10道题目为例

leetcode19. 删除链表的倒数第N个节点

题目描述

题目分析

1. 单链表只能单向走（尽可能在遍历一次的基础上找到答案）
2. 单纯的遍历找不到答案，采用双指针
3. 两个指针间距n，一个指针走到末尾，那么另外一个指针的位置就是在倒数第n+1个节点上

做题步骤

1. 建立虚拟头节点
2. fast向前走n步
3. fast与last同时向后走，fast走到末尾时终止
4. 进行删除操作

代码示例

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {auto dummy = new ListNode(-1);dummy->next = head;auto fast = dummy;auto last = dummy;while(n--){fast = fast->next;} while(fast->next != nullptr){fast = fast->next;last = last->next;}auto tmap = last->next;last->next = last->next->next;delete tmap;return dummy->next;}
};

leetcode 237. 删除链表中的节点

题目描述

题目分析

给一个节点将其删除（不是最后一个）
按照以前的删除做法不行（访问不到该节点的上一个节点）
将下一个节点覆盖到这个节点上，删除下一个节点

代码示例

class Solution {
public:void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;}
};

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

题目描述

题目分析

12. 要求删除重复元素
13. 保留第一个，删除以后重复的
14. 注意在取值的时候先进行判断指针是否存在

代码示例

class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {auto cur = head;while(cur){// 先进行判断指针的存在性if(cur->next && cur->val == cur->next->val){// auto tamp = cur->next;cur->next = cur->next->next;// delete tamp;}else{cur = cur->next;}}return head;}
};

leetcode 61.旋转链表

题目描述

题目分析

15. 先画图进行模拟
16. 发现可以直接整体进行移动
17. 但是需要先计算链表中节点的个数
18. 其余就与19题一样了，采用双指针做法
    代码示例

class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if(head==nullptr)   return head;int nums = 0;for(auto cur=head; cur; cur=cur->next){nums++;}k %= nums;auto fast = head;auto last = head;while(k--){fast = fast->next;}// 这里是访问到最后一个节点    假如是fast的话会访问到空指针while(fast->next){fast = fast->next;last = last->next;}fast->next = head;head = last->next;last->next = nullptr;return head;}
};

leetcode 24.两两交换链表中的节点

题目描述

题目分析

19. 这是每两个点作为一对进行交换
    那么就有以下几点需要注意
20. 需要知道这两个点，以及第一个点的前一个点
21. 交换时要注意顺序
22. 遍历时注意终止条件

代码示例

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head==nullptr || head->next==nullptr)    return head;auto dummy = new ListNode(-1);dummy->next = head;for(auto p = dummy; p->next && p->next->next;){auto left = p->next;auto right = left->next;p->next = right;left->next = right->next;right->next = left;p = left;}return dummy->next;}
};

leetcode 206.反转链表

题目分析

反转链表进行原地反转，只需进行考虑链表的节点反转次序
23. 需要记录当前节点的后一个
24. 需要进行反转，当前节点指向前一个
25. 移动到下一个

代码示例

class Solution {
public:ListNode* reverseList(ListNode* head) {if(head==nullptr || head->next==nullptr)    return head;auto pre = head;auto cur = pre->next;while(cur->next){auto after = cur->next;cur->next = pre;pre = cur;cur = after;}// cur的时候最后一个点没链接上cur->next = pre;head->next = nullptr;return cur;}
};

leetcode 92.反转链表Ⅱ

题目描述

题目分析

这个题目就是反转部分链表（给定区间上）
具体分为以下几个步骤
26. 反转区间上的链表
27. 将反转好的区间上的重新接到链表上
给出一个反转链表的模板
以下图为例

pre指向2
cur指向3

while(sum--){auto after = cur->next;cur->next = pre;pre = cur;cur = after;}

这段代码执行完之后 cur指向5， pre指向4

代码示例

class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {if(head==nullptr || head->next==nullptr || left==right)    return head;auto dummy = new ListNode(-501);dummy->next = head;int sum = right - left;auto a = dummy;for(int i=0; inext;auto pre = a->next;auto cur = pre->next;while(sum--){auto after = cur->next;cur->next = pre;pre = cur;cur = after;}a->next->next = cur;a->next = pre;return dummy->next;}
};

leetcode 160.相交链表

题目描述

题目分析

这个题要找两个链表的交点
暴力遍历复杂度是O(m*n)的时间复杂度
思考一下有这样的特点，两个链表的长度加上交点前的长度相等
代码示例

leetcode 142.环形链表

题目描述

题目分析

这道题目纯考数学能力

设置快慢指针，快指针走两步，慢指针走一步
设环的周长为c
慢指针走到c，那么快指针已经进圈，并且在圈里走了x，假设快指针距离交界点c为y
那么x+y=n∗cx+y=n*cx+y=n∗c
那么慢指针走y快指针必追上满指针
此时距离c点也是y
那么从开头到B点的距离就是yyy
那么再走x会回到点，因为x+y=n∗cx+y = n*cx+y=n∗c

代码示例

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {auto a = headA;auto b = headB;while(a != b){a = (a != NULL) ? a->next : headB;b = (b != NULL) ? b->next : headA;}return a;}
};

class Solution {
public:ListNode *detectCycle(ListNode *head) {auto fast = head;auto slow = head;while(fast){fast = fast->next;slow = slow->next;if(fast){fast = fast->next;}else{break;}if(fast == slow){slow = head;while(fast != slow){fast = fast->next;slow = slow->next;}return fast;}}return NULL;       }
};

leetcode 148.排序链表

题目描述

题目分析

说白了就是将链表进行排序
但是这道题目有一个要求

常数级空间复杂度则递归不行
只能用for循环的归并排序
步骤如下

1. 分组（以1，2，4，8分组）2k=n,k=log2n2^k=n, k=log_{2}{n}2k=n,k=log2​n
2. 每个组两两之间进行归并排序

代码示例

class Solution {
public:ListNode* sortList(ListNode* head) {auto dummy = new ListNode(-1);dummy->next = head;int n = 0;for(auto p=head; p; p=p->next)      ++n;for(int i=1; iauto cur = dummy;for(int j=0; j+iauto left = cur->next;auto right = cur->next;for(int m=0; mnext;int l = 0;int r = 0;while(lif(left->val <= right->val){cur->next = left;cur = left;left = left->next;++l;}else{cur->next = right;cur = right;right = right->next;++r;}}while(lcur->next = left;cur = left;left = left->next;++l;}while(rcur->next = right;cur = right;right = right->next;++r;}cur->next = right;}}return dummy->next;}
};