0603练习题目

06.03 第 026 ~ 037 题（第 09 ~ 12 天）

反转链表

迭代

使用两个指针 cur 和 pre 进行迭代。pre 指向 cur 前一个节点位置。初始时，pre 指向 None，cur 指向 head。不断让cur->next指向pre，pre右移，cur右移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 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 = NULL;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

递归

从 head.next 的位置开始调用递归函数，即将 head.next 为头节点的链表进行反转，并返回该链表的头节点。递归到链表的最后一个节点，将其作为最终的头节点，即为 new_head。在每次递归函数返回的过程中，改变 head 和 head.next 的指向关系。也就是将 head.next 的next 指针先指向当前节点 head，即 head.next.next = head 。然后让当前节点 head 的 next 指针指向 None，从而实现从链表尾部开始的局部反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 = NULL;
        return newHead;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)，最多需要n层栈空间。

反转链表II

分析

先让pre指向left的前一个节点，cur指向left，然后逐个反转，直到循环变量等于right。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * 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* reverseBetween(ListNode* head, int left, int right) {
        // 定义哑节点
        ListNode* dummy = new ListNode();
        dummy->next = head;
        // 定义pre cur指针
        ListNode* pre = dummy;
        ListNode* cur = head;
        // 先让cur指向left
        int i;
        for(i = 1; i < left; i++){
            pre = cur;
            cur = cur->next;
        }
        // 进行反转
        ListNode* next;
        for(; i < right; i++){
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummy->next;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

K个一组反转链表

分析

共需要反转n / k组，每组k个元素最后剩余的n % k个不需要反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 先得到链表的长度
        int n = 0;
        ListNode* cur = head;
        while(cur){
            n++;
            cur = cur->next;
        }
        // 计算要反转多少组
        int group = n / k;
        // 进行反转
        ListNode* dummy = new ListNode();
        dummy->next = head;
        ListNode* pre = dummy;
        cur = head;
        for(int i = 0; i < group; i++){
            // 保存反转前的尾部节点
            ListNode* gHead = cur;
            ListNode* gPrev = NULL;
            for(int j = 0; j < k; j++){
                ListNode* next = cur->next;
                cur->next = gPrev;
                gPrev = cur;
                cur = next;
            }
            // 连接起来
            pre->next = gPrev;
            gHead->next = cur;
            // 更新指针
            pre = gHead;
        }
        return dummy->next;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

[!NOTE]
这几道题回来再好好想想。

回文链表

分析

  1. 使用快慢指针找到中间位置。初始slow,fast = head,每次slow移动一步，fast移动两步，当fast->next指向空时，即到达链表表尾，此时slow所指的就是中间的位置。如果链表有偶数个元素，最后一次fast移动时只能移动一步。
  2. 反转后半部分链表。
  3. 比较两个部分的值，当后半部分到达末尾则比较完成，因为如果是偶数个，前半部分也会到达最后，如果是奇数个，前半部分最后一个节点无需判断。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * 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) {
        // 处理边界
        if(!head){
            return true;
        }
        // 分割链表
        ListNode* firstHalfEnd = cutList(head);
        // 反转后半部分
        ListNode* right = reverseList(firstHalfEnd->next);
        // 判断是否回文
        ListNode* left = head;
        while(right){
            if(left->val != right->val){
                return false;
            }
            left = left->next;
            right = right->next;
        }
        return true;
    }
    // 分割链表
    ListNode* cutList(ListNode* head){
        // 定义快慢指针
        ListNode* slow = head;
        ListNode* fast = head;
        // 移动双指针
        while(fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    // 反转链表
    ListNode* reverseList(ListNode* head){
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur){
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

合并两个有序链表

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * 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;
        // 不断比较list1和list2的值
        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)

排序链表

分析

快排在最坏情况下时间复杂度会到$O(n^2)$，在链表排序中一般选择归并排序。

  1. 分割环节：找到链表中心链节点，从中心节点将链表断开，并递归进行分割。
  2. 归并环节：将递归后的链表进行两两归并，完成一遍后每个子链表长度加倍。重复进行归并操作，直到得到完整的链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * 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* leftHead = head;
        ListNode* rightHead = slow->next;
        slow->next = NULL;
        // 递归排序左右两部分，合并两部分
        return merge(mergeSort(leftHead), mergeSort(rightHead));
    }
    // 合并链表
    ListNode* merge(ListNode* leftHead, ListNode* rightHead){
        // 定义哑节点
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        // 不断比较
        while(leftHead && rightHead){
            if(leftHead->val <= rightHead->val){
                cur->next = leftHead;
                leftHead = leftHead->next;
            }
            else{
                cur->next = rightHead;
                rightHead = rightHead->next;
            }
            cur = cur->next;
        }
        // 链接剩余部分
        while(leftHead){
            cur->next = leftHead;
            leftHead = leftHead->next;
            cur = cur->next;
        }
        while(rightHead){
            cur->next = rightHead;
            rightHead = rightHead->next;
            cur = cur->next;
        }
        return dummy->next;
    }
};
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

[!NOTE]
这一部分主要是链表的拆分，归并排序，使用到了快慢指针。即初始时快慢指针都指向head，慢指针每次走一步，快指针每次走两步，当快指针走到最后一个节点时，慢指针刚好走到中间位置。

合并K个升序链表

分治法

如果只剩一个链表，就结束递归。然后合并两个链表，按照归并排序的方式合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * 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 NULL;
        }
        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) / 2;
        ListNode* leftHead = mergeSort(lists, left, mid);
        ListNode* rightHead = mergeSort(lists, mid + 1, right);
        // 合并两部分
        return merge(leftHead, rightHead);
    }
    // 合并两个有序链表
    ListNode* merge(ListNode* leftHead, ListNode* rightHead){
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(leftHead && rightHead){
            if(leftHead->val <= rightHead->val){
                cur->next = leftHead;
                leftHead = leftHead->next;
            }
            else{
                cur->next = rightHead;
                rightHead = rightHead->next;
            }
            cur = cur->next;
        }
        // 剩余部分
        while(leftHead){
            cur->next = leftHead;
            leftHead = leftHead->next;
            cur = cur->next;
        }
        while(rightHead){
            cur->next = rightHead;
            rightHead = rightHead->next;
            cur = cur->next;
        }
        return dummy->next;
    }
};
  • 时间复杂度：力扣官方题解写的是，分治需要O(logk)，每次合并需要$O(2^in)$，但每次需要合并$\frac{k}{2^i}$组，因此算法时间复杂度接近$O(knlogk)$。但其他地方写的复杂度都是$O(nlogk)$。因为其他地方的n指的是所有链表节点的数目，而力扣的n是链表的最大节点数。
  • 空间复杂度：递归栈深度，O(logk)。

优先队列

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * 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* lhs, const ListNode* rhs){
            return lhs->val > rhs->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
        // 初始化一个哑节点
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        // 将每个链表的第一个节点放入最小堆
        for(auto& node : lists){
            if(node){
                heap.push(node);
            }
        }
        // 不断取堆顶元素加到结果链表中
        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)$，n是所有链表节点总数。
  • 空间复杂度：堆中的元素不超过k个，O(k)。

环形链表

分析

最简单的是申请一个哈希表或数组，标记每个节点是否访问过，但是题目进阶要求O(1)的空间复杂度。可以使用快慢指针，慢指针每次走一步，快指针每次走两步，如果快慢指针能够相遇，则说明存在环，否则快指针指向空，不存在环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * 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) {
        if(!head || !head->next){
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        // 移动快慢指针
        while(slow != fast && fast->next && fast->next->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        if(slow == fast){
            return true;
        }
        else{
            return false;
        }
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

环形链表II

分析

如果链表中有环，快慢两个指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了k步。由于快的指针一次走两步，因此在相遇时快的指针一共走了2k步。因此，到相遇时快的指针比慢的指针多走了k步。另外，两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数k一定是环中节点的数目的整数倍，此时慢的指针走过的步数k也是环中节点数的整数倍。

此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了k步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了k步，而k是环中节点的数目的整数倍，相当于前面的指针在环中转了k圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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) {
        // 处理边界情况
        if (!head || !head->next) {
            return NULL;
        }
        
        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)
  • 空间复杂度：O(1)

相交链表

分析

直观的想法是用哈希表记录链表的节点，但这样空间复杂度较高。创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。

  • pA指向空，将pA移向headB。
  • pB指向空，将pB移向headA。
  • 两者指向同一个节点或者都指向空，返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 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) {
        // 处理边界
        if(!headA || !headB){
            return NULL;
        }
        // 双指针
        ListNode* pA = headA;
        ListNode* pB = headB;
        while(pA != pB){
            pA = pA == NULL ? headB : pA->next;
            pB = pB == NULL ? headA : pB->next;
        }
        return pA;
    }
};
  • 时间复杂度：O(m + n)
  • 空间复杂度：O(1)

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

分析

很容易用遍历两遍的方法实现，考虑只扫描一次链表的方法。初始时两指针指向链表头部，快指针先走n步，然后快慢指针同时移动。当两指针走了len-n步，即快指针指向空时，慢指针指向倒数第n个节点。但是我们需要删除这个节点，所以让快指针指向最后一个节点，慢指针指向要删除的前一个节点，重置慢指针的next即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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(0, head);
        ListNode* slow = dummy;
        ListNode* fast = head;
        // 快指针先走n步
        for(int i = 0; i < n; i++){
            fast = fast->next;
        }
        // 两指针同时移动，直到fast指向空
        while(fast){
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* del = slow->next;
        slow->next = slow->next->next;
        delete(del);
        return dummy->next;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

重排链表

分析

直观的解法是是将链表遍历一遍，存入线性表中，但是这样需要消耗一定的空间。考虑寻找链表中点 + 链表逆序 + 合并链表。

  1. 寻找链表中点：可以用快慢指针，慢指针每次走一步，快指针每次走两步。当fast->next或者fast->next->next为空时，slow恰好指向中间。
  2. 逆序：将后半部分链表反转。
  3. 合并链表：按照第一个链表一个，第二个链表一个的顺序合并链表。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * 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) {
        // 处理边界
        if(!head || !head->next || !head->next->next){
            return;
        }
        // 找到中点
        ListNode* mid = findMid(head);
        ListNode* left = head;
        ListNode* right = mid->next;
        mid->next = nullptr; // 断开前后链表
        
        // 反转后半部分链表
        right = reverseList(right);
        
        // 合并
        mergeList(left, right);
    }

private:
    ListNode* findMid(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->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;
    }
    
    void mergeList(ListNode* left, ListNode* right){
        while(left && right){
            ListNode* leftNext = left->next;
            ListNode* rightNext = right->next;
            
            left->next = right;
            if(leftNext == nullptr) break; // 如果链表节点数是偶数，提前退出循环
            right->next = leftNext;
            
            left = leftNext;
            right = rightNext;
        }
    }
};
  • 时间复杂度：查找中点需要O(n)，反转也需要O(n)，合并也需要O(n)，因此最终为O(n)。
  • 空间复杂度：O(1)

总结

第 09 ~ 12 天的题目主要涉及分割链表，即找到链表的中点；反转链表，合并链表，以及使用双指针处理环形链表等。

算法笔记 > 面试篇
#leetcode-notes
0603练习题目
http://example.com/2024/10/23/posts/0603/
作者
Xuan Yang
发布于
2024年10月23日
许可协议