链表常用算法

合并两个有序链表

LeetCode: https://leetcode.cn/problems/merge-two-sorted-lists/

思路

遍历两个链表，每次比较两个链表节点的大小，将较小的节点接到结果链表上。

*技巧*：使用头节点避免 nullptr 的判断

代码

// Definition for singly-linked list.
// struct ListNode {
//   int val;
//   ListNode *next;
//   ListNode() : val(0), next(nullptr) {}
//   ListNode(int x) : val(x), next(nullptr) {}
//   ListNode(int x, ListNode *next) : val(x), next(next) {}
// };

class Solution {
public:
    // no head node
    // ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    //     if (list1 == nullptr) {
    //         return list2;
    //     }
    //     if (list2 == nullptr) {
    //         return list1;
    //     }
    //     ListNode* pos1 = nullptr;
    //     ListNode* pos2 = nullptr;
    //     ListNode* res = nullptr;
    //     if (list1->val < list2->val) {
    //         pos1 = list1;
    //         res = list1;
    //         pos2 = list2;
    //     } else {
    //         pos1 = list2;
    //         res = list2;
    //         pos2 = list1;
    //     }
    //     while (true) {
    //         if (pos1->next == nullptr) {
    //             pos1->next = pos2;
    //             return res;
    //         }
    //         if (pos2 == nullptr) {
    //             return res;
    //         }

    //         if (pos1->next->val < pos2->val) {
    //             pos1 = pos1->next;
    //         } else {
    //             ListNode* tmp = pos1->next;
    //             pos1->next = pos2;
    //             pos2 = pos2->next;
    //             pos1->next->next = tmp;
    //             pos1 = pos1->next;
    //         }
    //     }
    // }

    // head node
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode;
        ListNode* pos = head;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val < list2->val) {
                pos->next = list1;
                list1 = list1->next;
            } else {
                pos->next = list2;
                list2 = list2->next;
            }
            pos = pos->next;
        }
        if (list1 == nullptr) {
            pos->next = list2;
        }
        if (list2 == nullptr) {
            pos->next = list1;
        }
        ListNode* res = head->next;
        delete head;
        return res;
    }
};

合并 K 个有序链表

LeetCode: https://leetcode.cn/problems/merge-k-sorted-lists/

思路

将 K 个有序链表的头节点放入堆中
弹出堆顶节点，将节点的下一个节点放入堆中，并将节点接到结果链表
重复 2 ，知道处理完所有节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode;
        auto cmp = [](ListNode* left, ListNode* right) { return left->val > right->val; };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> min_queue(cmp);

        for (const auto& list : lists) {
            if (list != nullptr) {
                min_queue.push(list);
            }
        }

        ListNode* p = dummy;

        while (!min_queue.empty()) {
            ListNode* top = min_queue.top();
            min_queue.pop();
            p->next = top;
            if (top->next != nullptr) {
                min_queue.push(top->next);
            }
            p = p->next;
        }
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

技巧： priority_queue 自定义比较器，小根堆 cmp 是 > ，大根堆 cmp 是 <

删除链表倒数第 N 个节点

LeetCode: https://leetcode.cn/problems/remove-nth-node-from-end-of-list

思路

要删除第 N 个节点，先找到倒数第 N + 1 个节点
使用双指针指向头节点，第一个指针先前进 N + 1 个节点，然后两个指针同时前进，第一个指针到达 nullptr 时，第二个指针的位置就是倒数第 N + 1 个节点的位置
删除第 N 个节点

技巧：

头节点的使用，避免判断空指针
双指针

类似的问题：找出链表的中间节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode;
        dummy->next = head;

        ListNode* p1 = dummy;
        for (int i = 0; i < n + 1; i++) {
            p1 = p1->next;
        }
        ListNode* p2 = dummy;
        while (p1 != nullptr) {
            p1 = p1->next;
            p2 = p2->next;
        }

        ListNode* tmp = p2->next;
        p2->next = tmp->next;
        delete tmp;
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

判断链表是否存在环

LeetCode: https://leetcode.cn/problems/linked-list-cycle/

思路

使用快慢指针，均指向头节点，慢指针 p1 每一步移动一个节点，快指针 p2 每一步移动两个节点：

快慢指针均到达链表尾部 nullptr ，链表不存在环
快慢指针相遇，即 p1 = p2 ，链表存在环。

证明

定义：

\(l\) ：环的长度
\(s0\) ：慢指针进入环的起始位置
\(r1\) ：慢指针 p1 的移动速度
\(r2\) ：快指针 p2 的移动速度
\(s\) ：p1 刚进入环 \(s0\) 时，p2 距离 p1 的距离
\(m\) ：p1 刚进入环 \(s0\) 时，再移动 \(m\) 次即可与 p2 相遇

证明： \(r1\) 与 \(r2\) 满足什么条件时，p1 与 p2 一定会相遇。

根据以上定义，我们得到相遇时 p1 的位置为： \[ s0 + ((m*r1) \bmod l) \]

p2 的位置为： \[ s0 + ((m*r2 + s) \bmod l) \]

p1 与 p2 相遇等价于寻找一个 \(m\) ，使 \[ s0 + ((m*r1) \bmod l) = s0 + ((m*r2 + s) \bmod l) \] ~~化简得到：~~ 错误的化简 \[ m(r1 - r2) \equiv s\pmod{l} \]

由于 \(r1 - r2 < 0\) ，将左边加上 \(ml\) ，等式不变： \[ m(l + r1 - r2) \equiv s\pmod{l} \]

上面这个式子就是 线性同余方程 ，根据其性质，要使 \(m\) 一定有解，就必须满足 \[ gcd(l + r1 - r2, l) = 1 \]

对任意的 \(l\) ，当 \(|(l + r1 -r2) - l| = 1\) 时一定满足条件，即 \(r2 - r1 = 1\) 。

综上：链表成环的情况下，只要快指针比慢指针移动速度快一步，两者就一定能相遇。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }
};

进阶：找出环的起始节点

LeetCode: https://leetcode.cn/problems/linked-list-cycle-ii/

快慢指针相遇后，将慢指针置为头节点，然后快慢指针向前每次移动一步，快慢指针相遇的节点就是环的起始节点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }
        slow = head;
        while (slow != fast) {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

参考文章

https://labuladong.github.io/algo/di-ling-zh-bfe1b/shuang-zhi-0f7cc/ https://zhuanlan.zhihu.com/p/33663488 https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare https://blog.csdn.net/liuwp5/article/details/109207360

判断两个链表是否相交

LeetCode: https://leetcode.cn/problems/intersection-of-two-linked-lists/

思路

让 p1 遍历完链表 A 后，遍历链表 B ，p2 遍历完链表 B 后遍历链表 A ，在逻辑上拼接两条链表。拼接后 p1 和 p2 可以同时进入到相交节点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        while (p1 != p2) {
            if (p1 == nullptr) {
                p1 = headB;
            } else {
                p1 = p1->next;
            }
            if (p2 == nullptr) {
                p2 = headA;
            } else {
                p2 = p2->next;
            }
        }
        return p1;
    }
};

两两交换链表中的节点

思路

解法 1 ：模拟

解法 2 ：递归

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 模拟版本
    // ListNode* swapPairs(ListNode* head) {
    //     ListNode* dummy = new ListNode;
    //     ListNode* pos = dummy;
    //     pos->next = head;

    //     ListNode* p1 = head;
    //     ListNode* p2 = nullptr;

    //     while (p1 != nullptr && p1->next != nullptr) {
    //         p2 = p1->next;

    //         pos->next = p2;

    //         ListNode* tmp = p2->next;
    //         p2->next = p1;

    //         p1 = tmp;

    //         pos = pos->next->next;
    //         pos->next = p1;
    //     }

    //     ListNode* res = dummy->next;
    //     delete dummy;
    //     return res;
    // }

    // 递归版本
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }

};

反转链表

LeetCode: https://leetcode.cn/problems/reverse-linked-list/

思路

递归：先翻转子链表，然后将当前节点与子链表翻转，只需将当前节点放到子链表末尾。递归终止条件：子链表只有一个节点

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    // 迭代版本
    // ListNode* reverseList(ListNode* head) {
    //     if (head == nullptr) {
    //         return head;
    //     }

    //     ListNode* newTail = head;
    //     ListNode* newHead = head;
    //     ListNode* visit = head->next;

    //     while (visit) {
    //         ListNode* oldHead = newHead;
    //         newHead = visit;
    //         newTail->next = visit->next;
    //         visit = newHead->next;
    //         newHead->next = oldHead;
    //     }

    //     return newHead;
    // }

    // 递归版本
    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;
    }
};

进阶：翻转链表的一个区间

LeetCode: https://leetcode.cn/problems/reverse-linked-list-ii/

技巧：

递归结束条件的判断

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
static ListNode* last = nullptr;

class Solution {
public:
    // 递归版本
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (head == nullptr || head->next == nullptr || right == 1) {
            last = head->next; // 记录后面不需要翻转的节点
            return head;
        }

        auto newHead = reverseBetween(head->next, left - 1, right - 1);
        if (left <= 1) {
            head->next->next = head;
            head->next = last;
            return newHead;
        } else {
            head->next = newHead;
            return head;
        }
    }
};

判断回文字符串

LeetCode: https://leetcode.cn/problems/palindrome-linked-list/

思路

先利用快慢指针找出后半段链表
逆转后半段链表
依次比较，判断是否是回文字符串
恢复链表

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* preSlow = nullptr;

        while (fast != nullptr && fast->next != nullptr) {
            preSlow = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        if (fast != nullptr) {
            preSlow = slow;
            slow = slow->next;
        }


        ListNode* reversed = reverse(slow);


        ListNode* first = head;
        ListNode* second = reversed;
        bool result = true;
        while (second != nullptr) {
            if (first->val != second->val) {
                result = false;
                break;
            }
            first = first->next;
            second = second->next;
        }

        reversed = reverse(reversed);
        preSlow->next = reversed;

        return result;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

K 个一组反转链表

LeetCode: https://leetcode.cn/problems/reverse-nodes-in-k-group/

思路

从前到后，K 个一组反转链表即可

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* nextSubHead = head;
        ListNode* newHead = nullptr;
        ListNode* preTail = nullptr;
        ListNode* cur = head;
        while (nextSubHead != nullptr) {
            int i = 0;
            for (; i < k; i++) {
                if (nextSubHead == nullptr) {
                    break;
                }
                nextSubHead = nextSubHead->next;
            }
            if (i != k) {
                break;
            }

            ListNode* pre = nextSubHead;
            ListNode* tail = cur;
            while (cur != nextSubHead) {
                ListNode* next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
            if (preTail != nullptr) {
                preTail->next = pre;
            }
            preTail = tail;
            if (newHead == nullptr) {
                newHead = pre;
            }
        }

        return newHead ? newHead : head;
    }
};

文章目录