文章目录

• 一、链表
• 二、刷题
• • • 快慢指针类型题目汇总

一、链表

结构：$1$->$2$->$3$->NULL，链表是 指向型结构
查找：随机访问的时间复杂度是 O(n)。
增删：删除和插入元素的时间复杂度都是 O(1) 。

头结点：对于链表我们都用头结点 head来代表整个链表，给你一个链表的时候我们拿到的就是头节点 head。如果没有头结点证明整个链表为空 NULL，如果已经有头结点证明链表不为空。

==虚拟头结点 dummy：由于链表中是用头节点 head来代替整个链表的，故头节点 head经常需要判断头结点 head 有还是没有来进行不同的操作，可以通过设置一个哨兵节点 dummy的技巧简化代码，哨兵节点 dummy的值一直是 NULL，不用考虑其自身的问题。最后返回的是 dummy->next，因为我们已经不在乎head 是不是之前的 head了，保持 next即可。

// 虚拟头节点的链表遍历dummy; dumm->next = head; p = dummy;while (p) {}

// 没有虚拟头结点的链表遍历head;while (head){    head = head->next;}

二、刷题

LeetCode 206 反转链表 原题链接

    注意：对于分析算法题里有一个重要的理念，上来要考虑到入口的边界条件。

public:    ListNode* reverseList(ListNode* head) { if (!head) return head; ListNode* pre = NULL; ListNode* cur = head; while (cur) {     auto next = cur->next;     cur->next = pre;     pre = cur;     cur = next; } return pre;    }};

 
LeetCode 剑指 Offer 22. 链表中倒数第k个节点 原题连接

    $(1)$ 要求链表的倒数第 k个节点，假设链表的总长度为 n，n未知；
    $(2)$ 定义一个快指针 fast和一个慢指针slow，先让fast指针走 k步，直到 fast指针走到NULL，慢指针 slow走了 n - k步，慢指针 slow对应的节点就是倒数第 k个节点；

class Solution {public:    ListNode* getKthFromEnd(ListNode* head, int k) { auto fast = head; auto slow = head; while (fast && k) {     fast = fast->next;     k --; } while (fast) {     slow = slow->next;     fast = fast->next; } return slow;    }};

 
LeetCode 92 反转链表II 原题链接

class Solution {public:    ListNode* reverseBetween(ListNode* head, int left, int right) { auto dummy = new ListNode(-1); dummy->next = head; auto tmp = dummy; for (int i = 0; i < left - 1; i ++)     tmp = tmp->next;  auto pre = tmp->next; auto cur = pre->next; for (int i = 0; i < right - left; i ++) {     auto next = cur->next;     cur->next = pre;     pre = cur;     cur = next; } tmp->next->next = cur; tmp->next = pre; return dummy->next;    }};

 
LeetCode 21 合并两个有序链表 原题链接

    二路归并的方法

class Solution {public:    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { auto p = list1, q = list2; auto dummy = new ListNode(-1); auto cur = dummy; while (p && q) {     if (p->val <= q->val)      {  cur->next = p;  p = p->next;  cur = cur->next;     }     else     {  cur->next = q;  q = q->next;  cur = cur->next;     } } if (p) cur->next = p; if (q) cur->next = q; return dummy->next;    }};

快慢指针类型题目汇总

LeetCode 19 删除链表的第N个节点 原题链接

    $(1)$ 涉及到删除头结点的时候要用到虚拟头结点 dummy；
    $(2)$ 快指针 fast先走 n 步，然后快指针 fast和慢指针 slow同时走，直到快指针 fast走到终点，慢指针就走到了要删除点的前一个点，然后删除即可；

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

 
LeetCode 876 链表的中间节点 原题链接

    模拟枚举，奇数个节点的时候 fast->next为空 NULL，偶数个节点的时候 fast为空 NULL。

class Solution {public:    ListNode* middleNode(ListNode* head) { auto slow = head, fast = head; while (fast && fast->next) // &&  {     slow = slow->next;     fast = fast->next->next; }  return slow;    }};

 
LeetCode 234 回文链表 原题链接

    $(1)$ 链表不能直接通过索引找到链表的结尾；
    $(2)$ 找到链表的中点(分奇数个节点和偶数个节点)，然后将中点的前半段进行翻转，再依次遍历这两段链表，对比是否相同；

class Solution {public:    bool isPalindrome(ListNode* head) { auto slow = head, fast = head; ListNode* pre = NULL; while (fast && fast->next) {     fast = fast->next->next; // fast必须先走，因为后走之后，slow改变了原来的指针指向，fast就到不了该到的位置了         auto next = slow->next;     slow->next = pre;     pre = slow;     slow = next;   } if (fast) slow = slow->next; while (pre && slow) {     if (slow->val != pre->val) return false;     pre = pre->next;     slow = slow->next; } return true;    }};

 
LeetCode 160 相交链表 原题链接

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

 
LeetCode 141 环型链表 原题链接
    $(1)$ 通过两指针是否相遇来区分是否有环，相遇即有环，不相遇即无环；
    $(2)$ 有环相当于在环形操场跑，快指针跑的快就一定会和慢指针套圈，两指针定会相遇。无环相当于在直道跑，快指针跑的快，两指针一定不会遇到；

class Solution {public:    bool hasCycle(ListNode *head) { auto slow = head, fast = head; while (fast && fast->next) {     fast = fast->next->next;     slow = slow->next;     if (slow == fast) return true; } return false;    }};

 
LeetCode 142. 环形链表 II 原题链接

    $(1)$ fast指针一次走两步，slow指针一次走一步；
    $(2)$ fast指针走过的路程：$a+b+n(b+c)$，slow指针走过的路程 $a+b$，根据时间相等得到： $a+b$ = $(a+b+n(b+c))/2$；
    $(3)$ 对上面的公式进行移项化简，$a=n(b+c)-b$，$a=(n-1)(b+c)+c$；当两指针相遇之后，一个指针从头结点 head出发，另一个指针从相遇点出发，两指针以相同速度走，直到相遇为止，相遇的点就是链表环的入口节点；

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