LCR024-LCR027反转链表

剑指offer（专项突破版）4.4 反转链表

LCR024.反转链表

分析

对于每一个要转换其next指针的结点，需要保存它的前驱和后继，先让它的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
/**
 * 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 *prev = NULL;  // 头结点前驱
        ListNode *cur = head;   // 当前要转换的结点
        while(cur){
            ListNode *next = cur->next; // 保存当前结点的后继
            cur->next = prev;   // 转换指向
            prev = cur; // 更新前驱结点
            cur = next; // 更新当前结点
        }
        return prev;
    }
};

变量cur指向当前遍历到的节点，变量prev指向当前节点的前一个节点，而变量next指向下一个节点。每遍历一个节点之后，都让变量prev指向该节点。在遍历到尾节点之后，变量prev最后一次被更新，因此，变量prev最终指向原始链表的尾节点，也就是反转链表的头节点。

显然，上述代码的时间复杂度是O（n），空间复杂度是O（1）。

LCR025.链表中的两数相加

分析

把两个链表反转，再相加，得到的和链表再反转。

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
/**
 * 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 *prev = NULL;
        ListNode *cur = head;
        while(cur){
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
            
        }
        return prev;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *num1 = reverseList(l1);
        ListNode *num2 = reverseList(l2);
        ListNode *node = new ListNode(0);
        ListNode *res = node;
        int carry = 0;
        while(num1 && num2){
            int sum = num1->val + num2->val + carry;
            carry = sum / 10;
            ListNode *cur = new ListNode(sum % 10);
            res->next = cur;
            num1 = num1->next;
            num2 = num2->next;
            res = res->next;
        }
        while(num1){
            int sum = num1->val + carry;
            carry = sum / 10;
            ListNode *cur = new ListNode(sum % 10);
            res->next = cur;
            num1 = num1->next;   
            res = res->next;         
        }
        while(num2){
            int sum = num2->val + carry;
            carry = sum / 10;
            ListNode *cur = new ListNode(sum % 10);
            res->next = cur;
            num2 = num2->next;
            res = res->next;             
        }
        if(carry){
            ListNode *cur = new ListNode(1);
            res->next = cur;
        }
        node = node->next;
        res = reverseList(node);
        return res;       
    }
};
  • 时间复杂度：O(max(m, n))。
  • 空间复杂度：需要使用额外的空间来存储反转后的两个链表和最终的结果链表，它们的长度分别是 max(m, n)，因此空间复杂度为 O(max(m, n))。

LCR025结果

LCR026.重排链表

分析

把链表分成两部分，后半部分逆转，再分别与前半部分的结点连接起来。要找到中间结点，可以使用快慢指针。

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
68
69
70
71
72
73
74
75
/**
 * 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) {}
 * };
 */
 
 // 找到中间结点
 ListNode* findMidNode(ListNode *head){
    // 快慢指针法
    ListNode *slow = head->next;
    ListNode *fast = slow->next;
    while(fast->next){
        slow = slow->next;
        fast = fast->next;
        if(fast->next){
            fast = fast->next;
        }
        else{
            break;
        }
    }
    return slow;
 }
 // 反转链表
 ListNode* reverseList(ListNode *head){
    ListNode *cur = head;
    ListNode *prev = NULL;
    while(cur){
        ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
 }

class Solution {
public:
    void reorderList(ListNode* head) {
        // 处理边界
        if(!head->next || !head->next->next){
            return;
        }
        // 使用哨兵结点
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        // 找到中间结点
        ListNode *mid = findMidNode(head);
        // 后半部分反转
        mid = reverseList(mid);
        // 连接起来
        ListNode *prev = dummy;
        ListNode *first = head;
        ListNode *second = mid;
        while(first && second && first != second){
            // 记录下一个
            ListNode *fnext = first->next;
            ListNode *snext = second->next;
            // first连接到prev
            prev->next = first;
            // second连接到first
            first->next = second;
            // 移动prev,first,second
            prev = second;
            first = fnext;
            second = snext;
        }
    }
};

  • 时间复杂度：
    • 找到中间节点：采用快慢指针法，时间复杂度为 O(n)，其中 n 是链表的长度。
    • 反转后半部分链表：采用迭代方式，时间复杂度为 O(n)，其中 n 是后半部分链表的长度。
    • 合并两个链表：在合并过程中，每次迭代都会连接一个节点，因此时间复杂度也是 O(n)，其中 n 是链表的长度。
  • 空间复杂度：O(1)

LCR026结果

LCR027.回文链表

分析

和LCR026的思路是一样的，先找到中间结点，再把后半部分进行反转，然后比较是否相同。

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
/**
 * 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* findMidNode(ListNode *head){
        ListNode *slow = head;
        ListNode *fast = head->next;
        while(fast->next){
            slow = slow->next;
            fast = fast->next;
            if(fast->next){
                fast = fast->next;
            }
        }
        return slow;
    }
    // 反转链表
    ListNode* reverseList(ListNode *head){
        ListNode *cur = head;
        ListNode *prev = NULL;
        while(cur){
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    bool isPalindrome(ListNode* head) {
        if(!head->next){
            return true;
        }
        // 找到中间结点（前半部分的最后一个结点）
        ListNode *mid = findMidNode(head);
        // 反转后半部分
        ListNode *back = reverseList(mid->next);
        // 判断两部分是否相等
        ListNode *fore = head;
        while(fore && back){
            if(fore->val != back->val){
                return false;
            }
            fore = fore->next;
            back = back->next;
        }
        return true;
    }
};

LCR027结果

总结

  • 反转链表操作：在反转链表时，需要使用三个指针来记录当前节点、前驱节点和后继节点，然后依次更新它们的指针，实现链表的反转。这个过程需要注意保存链表的头结点和边界条件的处理。
  • 利用快慢指针找中间节点：在某些情况下，需要找到链表的中间节点，可以利用快慢指针的方法。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针则指向链表的中间节点。
算法笔记 > 链表
#剑指Offer
LCR024-LCR027反转链表
http://example.com/2024/04/18/posts/LCR024/
作者
Xuan Yang
发布于
2024年4月18日
许可协议