【LeetCode】链表精选11题

快慢指针：

1. 相交链表（简单）

2. 环形链表（简单）

3. 快乐数（简单）

4. 环形链表 II（中等）

5. 删除链表的倒数第 N 个节点（中等）

递归迭代双解法：

1. 合并两个有序链表（简单）

1.1 递归求解

1.2 迭代求解

2. 反转链表（简单）

2.1 递归求解

2.2 迭代求解

3. 两两交换链表中的节点（中等）

3.1 递归求解

3.2 迭代求解

4. 合并 K 个升序链表（困难）

4.1 递归解法

4.2 迭代解法

综合题：

1. 重排链表（中等）

2. K个一组翻转链表（困难）

快慢指针：

1. 相交链表（简单）

找两个链表的尾结点，尾结点不相同则不相交。假设相交，长短链表之间差距gap步。假设i指向长链表的头节点，j指向短链表的头节点，i先走gap步，然后ij同时走，每次走1步。当ij相遇时，相遇点就是相交点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 找两个链表的尾结点，尾结点不相同则不相交
        ListNode* tailA = headA;
        ListNode* tailB = headB;
        int lenA = 0;
        int lenB = 0;
        while (tailA->next)
        {
            ++lenA;
            tailA = tailA->next;
        }
        while (tailB->next)
        {
            ++lenB;
            tailB = tailB->next;
        }
        if (tailA != tailB)
            return nullptr;

        // 判断长短链表
        ListNode* longList = headA;
        ListNode* shortList = headB;
        if (lenB > lenA)
        {
            longList = headB;
            shortList = headA;
        }

        // 长链表先走gap步
        int gap = abs(lenA - lenB);
        while (gap--)
        {
            longList = longList->next;
        }
        
        // 同时走，找交点
        while (longList != shortList)
        {
            longList = longList->next;
            shortList = shortList->next;
        }
        return longList;
    }
};

2. 环形链表（简单）

慢指针每次走1步，快指针每次走2步，慢指针进环后，快指针一定能追上慢指针，它们会在环中某点相遇。

为什么慢指针每次走1步，快指针要每次走2步，它们才能相遇？

假设慢指针进环时，快慢指针之间差距gap步。

如果快指针每次走2步，每走一次，它们之间的差距减1，gap一定会减到0。

如果快指针每次走3步，每走一次，它们之间的差距减2。如果gap为偶数，gap一定会减到0。如果gap为奇数，gap会减到-1，表示它们之间的距离变成C - 1（C是环的周长），如果C - 1是偶数，它们会相遇，如果C - 1是奇数，它们永远不会相遇。

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

3. 快乐数（简单）

不是链表题，但是和上一题“环形链表”类似，慢指针每次走1步，快指针每次走2步，慢指针进环后，快指针一定能追上慢指针，它们会在环中某点相遇。如果相遇点为1，则为快乐数，否则不是快乐数。这里的指针表示的是值本身。

class Solution {
public:
    bool isHappy(int n) {
        int slow = n;
        int fast = bitSquareSum(n);
        while (slow != fast)
        {
            slow = bitSquareSum(slow);
            fast = bitSquareSum(bitSquareSum(fast));
        }
        return slow == 1;
    }

private:
    // 计算n的每一位的平方和
    int bitSquareSum(int n)
    {
        int sum = 0;
        while (n)
        {
            int tmp = n % 10;
            sum += tmp * tmp;
            n /= 10;
        }
        return sum;
    }
};

4. 环形链表 II（中等）

慢指针每次走1步，快指针每次走2步，慢指针进环后，快指针一定能追上慢指针，它们会在环中某点相遇。

假设在相遇点，慢指针一共走了k步，那么快指针一定一共走了2k步，所以快指针比慢指针多走了k步。另外，在相遇点，快指针一定比慢指针在环中多走了若干圈。所以，k一定是环的周长（环中节点个数）的整数倍。

此时，让i指向相遇点，j指向链表头节点，它们之间差距k步（慢指针走过的步数），如果i到达了环的入口，j也一定到达了环的入口，因为它们之间差距k步，k一定是环的周长的整数倍。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) // 相遇
            {
                ListNode* i = slow; // 相遇点
                ListNode* j = head;
                while (i != j)
                {
                    i = i->next;
                    j = j->next;
                }
                return i;
            }
        }
        return nullptr;
    }
};

5. 删除链表的倒数第 N 个节点（中等）

快指针先走n步，然后快慢指针同时走，每次走1步。当快指针指向最后一个节点时，慢指针指向倒数第n + 1个节点。

例如，删除链表的倒数第2个节点：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* preHead = new ListNode(0, head); // 哨兵节点
        ListNode* fast = preHead; // 快指针
        ListNode* slow = preHead; // 慢指针
        // 快指针先走n步
        while (n--)
        {
            fast = fast->next;
        }
        // 快慢指针同时走，每次走1步，直到快指针走到最后一个节点停止
        while (fast->next)
        {
            fast = fast->next;
            slow = slow->next;
        }
        // 此时慢指针指向倒数第n+1个节点
        // 让倒数第n+1个节点的next域直接指向倒数第n-1个节点
        slow->next = slow->next->next;
        return preHead->next;
    }
};

递归迭代双解法：

1. 合并两个有序链表（简单）

1.1 递归求解

重复的子问题——函数头设计

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)

子问题在做什么——函数体设计

选择两个链表的头节点中值较小的那一个作为最终合并的新链表的头节点，然后将剩下的链表交给递归函数去处理。

比较list1->val和list2->val的大小（假设list1->val较小）
list1->next = mergeTwoLists(list1->next, list2);
return list1;

递归出口

当某一个链表为空的时候，返回另外一个链表。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        if (list1->val < list2->val)
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else
        {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

1.2 迭代求解

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* preHead = new ListNode; // 哨兵节点
        ListNode* tail = preHead;

        // 取小的尾插
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                tail->next = list1;
                tail = tail->next;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
                list2 = list2->next;
            }
        }

        if (list1)
        {
            tail->next = list1;
        }
        if (list2)
        {
            tail->next = list2;
        }

        return preHead->next;
    }
};

2. 反转链表（简单）

2.1 递归求解

重复的子问题——函数头设计

ListNode* reverseList(ListNode* head)

子问题在做什么——函数体设计

将当前结点之后的链表反转，然后把当前结点添加到反转后的链表后面即可，返回反转后的头节点。

ListNode* newHead = reverseList(head->next);
head->next->next = head; head->next = nullptr;
return newHead;

递归出口

当前结点为空或者当前只有一个结点的时候，不用反转，直接返回。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

2.2 迭代求解

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
};

3. 两两交换链表中的节点（中等）

3.1 递归求解

重复的子问题——函数头设计

ListNode* swapPairs(ListNode* head)

子问题在做什么——函数体设计

将从第三个节点开始的链表两两交换节点，然后再把前两个节点交换一下，链接上刚才处理过的链表，并返回。

ListNode* tmp = swapPairs(head->next->next);
ListNode* newHead = head->next; newHead->next = head;
head->next = tmp;
return newHead;

递归出口

当前结点为空或者当前只有一个结点的时候，不用两两交换，直接返回。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* tmp = swapPairs(head->next->next);
        ListNode* newHead = head->next;
        newHead->next = head;
        head->next = tmp;
        return newHead;
    }
};

3.2 迭代求解

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* preHead = new ListNode(0, head); // 哨兵节点
        ListNode* cur = preHead;
        // cur后面的两个节点交换
        while (cur->next && cur->next->next)
        {
            ListNode* node1 = cur->next;
            ListNode* node2 = cur->next->next;
            cur->next = node2;
            node1->next = node2->next;
            node2->next = node1;
            cur = node1;
        }
        return preHead->next;
    }
};

4. 合并 K 个升序链表（困难）

4.1 递归解法

分治的思想，类似归并排序：

划分两个子区间
分别对两个子区间的链表进行合并，形成两个有序链表
合并两个有序链表

重复的子问题——函数头设计

ListNode* merge(vector<ListNode*>& lists, int begin, int end)

子问题在做什么——函数体设计

划分两个子区间：int mid = (begin + end) / 2;
递归合并两个子区间：
ListNode* l1 = merge(lists, begin, mid);
ListNode* l2 = merge(lists, mid + 1, end);
合并两个有序链表：return mergeTowList(l1, l2);

递归出口

当区间只有一个链表时，不合并。另外，当题目给出空链表时，不合并。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }

private:
    ListNode* merge(vector<ListNode*>& lists, int begin, int end)
    {
        if (begin > end)
            return nullptr;
        if (begin == end)
            return lists[begin];

        int mid = (begin + end) / 2;
        ListNode* l1 = merge(lists, begin, mid);
        ListNode* l2 = merge(lists, mid + 1, end);
        return mergeTwoLists(l1, l2);
    }
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
    {
        ListNode* preHead = new ListNode; // 哨兵节点
        ListNode* tail = preHead;

        // 取小的尾插
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                tail->next = list1;
                tail = tail->next;
                list1 = list1->next;
            }
            else
            {
                tail->next = list2;
                tail = tail->next;
                list2 = list2->next;
            }
        }

        if (list1)
        {
            tail->next = list1;
        }
        if (list2)
        {
            tail->next = list2;
        }

        return preHead->next;
    }
};

4.2 迭代解法

和“合并两个有序链表”类似，就是取小的尾插。怎么判断K个链表未合并的头节点中最小的那个？利用堆这个数据结构即可。把K个链表未合并的头节点放进一个小根堆，堆顶就是最小的那个。

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 创建小根堆
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
        // 将所有头节点放进小根堆
        for (auto& l : lists)
        {
            if (l)
            {
                heap.push(l);
            }
        }
        // 合并链表
        ListNode* preHead = new ListNode; // 哨兵节点
        ListNode* tail = preHead;
        while (!heap.empty())
        {
            // 取堆顶节点尾插
            tail->next = heap.top();
            heap.pop();
            tail = tail->next;
            // 将刚才合并的节点的下一个节点补充进堆
            if (tail->next)
            {
                heap.push(tail->next);
            }
        }
        return preHead->next;
    }

private:
    struct cmp
    {
        bool operator()(ListNode* n1, ListNode* n2)
        {
            return n1->val > n2->val;
        }
    };
};

综合题：

1. 重排链表（中等）

把链表后半段反转，再合并起来：

链表长度是偶数：1 2 3 4 （2是中间节点）

1 2

4 3

合并起来：1 4 2 3

链表长度是奇数：1 2 3 4 5 （3是中间节点）

1 2 3

5 4（4 5反转）

合并起来：1 5 2 4 3

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* mid = midNode(head);
        ListNode* l2 = reverseList(mid->next);
        mid->next = nullptr;
        ListNode* l1 = head;
        mergeLists(l1, l2);
    }

private:
    // 快慢指针找链表的中间节点，如果节点个数为偶数，取靠左的
    ListNode* midNode(ListNode* head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        // 慢指针每次走1步，快指针每次走2步
        // 如果节点个数为奇数，当快指针指向最后一个节点时，慢指针指向中间节点
        // 如果节点个数为奇数，当快指针指向倒数第二个节点时，慢指针指向靠左的中间节点
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    // 反转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    // 合并链表
    void mergeLists(ListNode* l1, ListNode* l2)
    {
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        while (cur1 && cur2)
        {
            ListNode* next1 = cur1->next;
            ListNode* next2 = cur2->next;
            cur1->next = cur2;
            cur2->next = next1;
            cur1 = next1;
            cur2 = next2;
        }
    }
};

2. K个一组翻转链表（困难）

头插法。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 求出需要翻转多少组
        int n = 0;
        ListNode* cur = head;
        while (cur)
        {
            cur = cur->next;
            n++;
        }
        n /= k;

        // 重复n次：长度为k的链表翻转
        ListNode* preHead = new ListNode; // 哨兵节点
        ListNode* pre = preHead;
        cur = head;
        for (int i = 0; i < n; i++)
        {
            ListNode* tmp = cur;
            for (int j = 0; j < k; j++)
            {
                ListNode* next = cur->next;
                cur->next = pre->next;
                pre->next = cur;
                cur = next;
            }
            pre = tmp;
        }

        // 把不需要翻转的部分接上
        pre->next = cur;
        
        return preHead->next;
    }
};