LeetCode 热题 100-链表

相交链表

双指针

相交链表

/**
 * 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* p = headA;
        ListNode* q = headB;
        // 循环直至p==q
        while(p != q){
            // p、q向后走
            p = p ? p->next : headB;
            q = q ? q->next : headA;
        }
        // 相交，则走到相交起始节点处；不相交，都走到空
        return p;
    }
};

时间复杂度：O(m+n)
空间复杂度：O(1)

反转链表

迭代

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

/**
 * 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) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

递归

如果当前链表为空，或者只剩下一个未反转，直接返回head。否则，先递归反转后续的所有节点，得到反转后的头，就是该链表新的头。再将当前节点next的next指向当前节点，注意将当前节点的next置空。

/**
 * 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 || !head->next){
            return head;
        }
        // 递归反转后边的节点
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return newHead;
    }
};

时间复杂度：O(n)
空间复杂度：O(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:
    bool isPalindrome(ListNode* head) {
        // 找到中点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next;
            if(fast){
                fast = fast->next;
            }
        }

        // 反转链表
        ListNode* mid = slow;
        ListNode* half = reverseList(mid);
        while(half){
            if(head->val != half->val){
                return false;
            }
            head = head->next;
            half = half->next;
        }
        return true;
    }

    // 反转链表
    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;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

重排链表

分析

和上题思路一样，找到中点，将后半部分反转，注意将中间断开，然后按照归并排序合并的方法重组链表。

/**
 * 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:
    void reorderList(ListNode* head) {
        // 找到中点
        ListNode* mid = findMid(head);
        // 逆转后半部分
        ListNode* half = reverseList(mid);
        // 合并
        ListNode* cur = head;
        while(half->next){
            ListNode* n1 = cur->next;
            ListNode* n2 = half->next;
            cur->next = half;
            half->next = n1;
            cur = n1;
            half = n2;
        }
    }

    // 找到中点
    ListNode* findMid(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->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;
    }
};

时间复杂度：O(n)
空间复杂度：O(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 && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                return true;
            }
        }

        return false;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

环形链表II

快慢指针

假设入环点距链表头为a，相遇点距入环点为b，相遇点到最后是c，则有a + n(b + c) = 2(a + b)，得到a = c + (n-1)(b+c)，即从链表头到入环点的距离等于从相遇点出发走了n-1次环的距离，即如果定义一个指针从链表头出发，一个指针从相遇点出发，每次都向后走一步，他们最终会相遇，相遇的地点就是入环点。

/**
 * 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;

        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            // 存在环
            if(slow == fast){
                ListNode* ptr = head;
                while(ptr != slow){
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return NULL;
    }
};

时间复杂度：O(n)，在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。
空间复杂度：O(1)

合并两个有序链表

归并排序

不断比较两链表的节点值，将较小的节点加入新链表，继续向后遍历。

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;

        while(list1 && list2){
            if(list1->val < list2->val){
                cur->next = list1;
                list1 = list1->next;
            }else{
                cur->next = list2;
                list2 = list2->next;
            }
            cur = cur->next;
        }

        // 链接剩余部分
        while(list1){
            cur->next = list1;
            list1 = list1->next;
            cur = cur->next;
        }
        while(list2){
            cur->next = list2;
            list2 = list2->next;
            cur = cur->next;
        }

        return dummy->next;
    }
};

时间复杂度：O(m+n)
空间复杂度：O(1)

两数相加

模拟

模拟从个位加到最高位即可，注意维护进位标志，如果最后的进位是1，还需要再加一个新节点。

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        int carry = 0;

        while(l1 && l2){
            int sum = l1->val + l2->val + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            cur->next = node;
            cur = cur->next;
            l1 = l1->next;
            l2 = l2->next;
        }

        // 剩余部分
        while(l1){
            int sum = l1->val + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            cur->next = node;
            cur = cur->next;
            l1 = l1->next;            
        }
        while(l2){
            int sum = l2->val + carry;
            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            cur->next = node;
            cur = cur->next;
            l2 = l2->next;            
        }
        // 判断进位
        if(carry){
            ListNode* node = new ListNode(carry);
            cur->next = node;
        }

        return dummy->next;
    }
};

时间复杂度：O(n)，n为两链表长度的较大值。
空间复杂度：O(1)，不计入返回结果的空间复杂度。

删除链表的倒数第n个结点

快慢指针

最简单的方法是遍历一遍链表，得到链表的长度，然后从头走len-n步即找到倒数第n个节点。考虑只遍历一次链表：让一个指针先走n步，然后两指针同时走，当先走的指针走到空时，即它又走了len-n步，那么从头出发的指针也走了len-n步，它所指向的就是倒数第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;

        // 先走n步
        ListNode* fast = dummy;
        for(int i = 0; i < n; i++){
            fast = fast->next;
        }

        // 同时走，找到要删除的节点的前一个节点
        ListNode* slow = dummy;
        while(fast->next){
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;  // 删除节点
        return dummy->next;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

如果要delete这个结点，可以先将它保存，再delete掉。

两两交换链表中的节点

迭代

定义哑节点方便操作，作为pre，定义当前指针left和下一个指针right，同时保存再下一个指针next，先让pre->next指向right，right->next指向left，left->next指向next。

/**
 * 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();
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* left = head;

        // 至少要有两个节点
        while(left && left->next){
            ListNode* right = left->next;
            ListNode* next = right->next;
            pre->next = right;
            right->next = left;
            left->next = next;

            pre = left;
            left = next;
        }

        return dummy->next;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

递归

递归结束：head为空或者head->next为空，返回head。

否则，先交换后面的链表，即递归调用swapPairs(head->next->next)，然后将head->next指向返回的链表头，而原来的next指向head，再返回next。

/**
 * 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) {
        // 递归结束
        if(!head || !head->next){
            return head;
        }

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

时间复杂度：O(n)
空间复杂度：O(n)

k个一组翻转链表

分析

首先统计链表节点个数，然后k 个一组处理，

Alt text

/**
 * 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) {
        // 统计结点个数
        int n = 0;
        ListNode* cur = head;
        while(cur){
            n++;
            cur = cur->next;
        }
        
        ListNode* dummy = new ListNode(0, head);
        ListNode* p0 = dummy;
        ListNode* pre = nullptr;
        cur = head;

        for(; n >= k; n-= k){
            // k个一组翻转链表
            for(int i = 0; i < k; i++){
                ListNode* nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }

            // 重新链接
            ListNode* nxt = p0->next;
            nxt->next = cur;
            p0->next = pre;
            p0 = nxt;
        }

        return dummy->next;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

随机链表的复制

回溯+哈希表

定义一个哈希表，用于存储节点的副本，如果这个节点已经存在，就直接返回，如果不存在，就复制一份，然后递归复制它的next和random。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> cache;    // 哈希表
    Node* copyRandomList(Node* head) {
        // 递归结束
        if(head == NULL){
            return head;
        }

        // 如果不存在，就创建
        if(!cache.count(head)){
            Node* newHead = new Node(head->val);
            cache[head] = newHead;
            // 递归创建指针副本
            newHead->next = copyRandomList(head->next);
            newHead->random = copyRandomList(head->random);
        }

        return cache[head];
    }
};

时间复杂度：O(n),其中 n 是链表的长度。对于每个节点，我们至多访问其「后继节点」和「随机指针指向的节点」各一次，均摊每个点至多被访问两次。
空间复杂度：O(n)，哈希表空间开销。

迭代+节点拆分

把每个节点复制一份链接在原节点的后边。
复制节点的random就是原节点的random的next。
分离链表。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 处理边界
        if(!head){
            return head;
        }

        // 复制链表节点
        for(Node* cur = head; cur != NULL; cur = cur->next->next){
            cur->next = new Node(cur->val, cur->next, NULL);    // random暂时置空
        }

        // 链接random
        for(Node* cur = head; cur; cur = cur->next->next){
            // 注意cur->random需要不为空才能这样操作
            if(cur->random){
                cur->next->random = cur->random->next;
            }      
        }

        // 分离链表
        Node* newHead = head->next;
        for(Node* cur = head; cur; cur = cur->next){
            Node* copy = cur->next;
            cur->next = copy->next;
            // 需要注意copy的next不能为空
            copy->next = copy->next ? copy->next->next : NULL;
        }

        return newHead;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)，不计入返回值。

排序链表

归并排序（递归）

分割环节：找到链表中心链节点，从中心节点将链表断开，并递归进行分割。
归并环节：将递归后的链表进行两两归并，完成一遍后每个子链表长度加倍。重复进行归并操作，直到得到完整的链表。

/**
 * 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* sortList(ListNode* head) {
        return mergeSort(head);
    }

    ListNode* mergeSort(ListNode* head){
        // 处理边界
        if(!head || !head->next){
            return head;
        }
        // 先找到链表的中间结点的前一个节点
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        // 断开链接
        ListNode* mid = slow->next;
        slow->next = nullptr;

        ListNode* left = head;
        ListNode* right = mid;

        // 递归排序两部分并合并
        return merge(mergeSort(left), mergeSort(right));
    }

    ListNode* merge(ListNode* left, ListNode* right){
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(left && right){
            if(left->val < right->val){
                cur->next = left;
                left = left->next;
            }else{
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        // 链接剩余部分
        cur->next = left ? left : right;
        return dummy->next;
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(logn)，递归需要 O(logn) 的栈开销。

归并排序（迭代）

具体算法：

遍历链表，获取链表长度 length。
初始化步长 step=1。
循环直到 step≥length。
每轮循环，从链表头节点开始。
分割出两段长为 step 的链表，合并，把合并后的链表插到新链表的末尾。重复该步骤，直到链表遍历完毕。
把 step 扩大一倍。回到第 4 步。

迭代的方法有些难理解，晚上有时间再看吧。

合并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* mergeKLists(vector<ListNode*>& lists) {
        int k = lists.size();
        if(k == 0){
            return nullptr;
        }
        
        return mergeSort(lists, 0, k-1);
    }

    ListNode* mergeSort(vector<ListNode*>& lists, int left, int right){
        // 递归结束
        if(left == right){
            return lists[left];
        }
        // 递归合并
        int mid = (left + right) >> 1;
        return merge(mergeSort(lists, left, mid), mergeSort(lists, mid+1, right));
    }

    ListNode* merge(ListNode* leftList, ListNode* rightList){
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(leftList && rightList){
            if(leftList->val < rightList->val){
                cur->next = leftList;
                leftList = leftList->next;
            }else{
                cur->next = rightList;
                rightList = rightList->next;
            }
            cur = cur->next;
        }
        cur->next = leftList ? leftList : rightList;

        return dummy->next;
    }
};

时间复杂度：O(nlogk)，其中 k 为 lists 的长度，n 为所有链表的节点数之和。每个节点参与链表合并的次数为 O(logk) 次，一共有 n 个节点，所以总的时间复杂度为 O(nlogk)。
空间复杂度：O(logk)，递归栈消耗的空间。

优先队列

维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，可以用优先队列来优化这个过程。

/**
 * 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) {
        // 最小堆
        auto cmp = [&](const ListNode* a, ListNode* b){
            return a->val > b->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
        // 将每个链表的第一个节点放入最小堆
        for(auto head : lists){
            if(head) heap.push(head);
        }        

        // 初始化一个哑节点
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;

        while(!heap.empty()){
            ListNode* node = heap.top();
            heap.pop();
            if(node->next){
                heap.push(node->next);
            }
            // 将当前堆中最小节点链接到答案
            cur->next = node;
            cur = cur->next;
        }
        return dummy->next;
    }
};

时间复杂度：O(nlogk)，其中 k 为 lists 的长度，n 为所有链表的节点数之和。
空间复杂度：O(k)，最小堆中最多包含k个元素。

LRU缓存

双向链表

class Node {
public:
    int key;
    int value;
    Node* prev;
    Node* next;

    Node(int k = 0, int v = 0) : key(k), value(v) {}
};

class LRUCache {
public:
    LRUCache(int capacity) : capacity(capacity) {
        dummy = new Node();
        dummy->prev = dummy;
        dummy->next = dummy;
    }
    
    int get(int key) {
        Node* node = getNode(key);
        return node ? node->value : -1;
    }
    
    void put(int key, int value) {
        Node* node = getNode(key);
        // 如果已经存在，就更新value
        if(node){
            node->value = value;
        }else{
            // new一个新节点加入哈希表
            hash[key] = new Node(key, value);
            pushFront(hash[key]);
            // 如果超出容量
            if(hash.size() > capacity){
                // 去掉最后一本书
                Node* backNode = dummy->prev;
                hash.erase(backNode->key);
                remove(backNode);
                delete backNode;
            }
        }
    }

private:
    int capacity;
    Node* dummy;
    unordered_map<int, Node*> hash;

    // 删除一个节点
    void remove(Node* x){
        x->prev->next = x->next;
        x->next->prev = x->prev;
    }

    // 在链表头添加一个节点
    void pushFront(Node* x){
        x->prev = dummy;
        x->next = dummy->next;
        x->prev->next = x;
        x->next->prev = x;
    }

    // 获取key对应的节点，同时移到表头
    Node* getNode(int key){
        auto it = hash.find(key);
        // 如果不存在
        if(it == hash.end()){
            return NULL;
        }
        Node* node = it->second;
        remove(node);   // 移出
        pushFront(node);    // 放到最上面
        return node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

时间复杂度：所有操作均为 O(1)。
空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。

之后有时间可以练一下LFU缓存。

算法笔记 > 链表

#leetcode-hot100

LeetCode 热题 100-链表

http://example.com/2024/11/29/posts/hot100-7/

作者

Xuan Yang

发布于

2024年11月29日

许可协议

LeetCode 热题 100-二叉树上一篇

LeetCode 热题 100-矩阵下一篇