2026/04/07

[LeetCode] 143 Reorder List

reverseList最後要把node->next重設為nullptr, 此時node是尾巴
不然node->next會指向區域變數prev
AddressSantizer會抱錯
  
 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
/**
 * 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* takeOneStep(ListNode *node) {
    if (!node)
      return nullptr;
    return node->next;
  }

  ListNode* takeTwoStep(ListNode *node) {
    return takeOneStep(takeOneStep(node));
  }

  ListNode* findMiddle(ListNode* node) {
    ListNode* slow = node;
    ListNode* fast = node;
    ListNode* slowNext = takeOneStep(slow);
    ListNode* fastNext = takeTwoStep(fast);
    while(slowNext && fastNext) {
      slow = slowNext;
      fast = fastNext;
      slowNext = takeOneStep(slow);
      fastNext = takeTwoStep(fast);
    }
    return slow;
  }

  ListNode* reverseList(ListNode* node) {
    ListNode* prev = nullptr;
    ListNode* next = nullptr;
    ListNode* cur = node;
    while (cur) {
      next = cur->next;
      cur->next = prev;
      prev = cur;
      cur = next;
    }

    // Avoid heap-use-after-free in AddressSanitizer
    node->next = nullptr;
    return prev;
  }

  ListNode* mergeList(ListNode* node1, ListNode* node2) {
    ListNode* tmp1 = nullptr;
    ListNode* tmp2 = nullptr;
    while (node1 && node2) {
      tmp1 = node1->next;
      tmp2 = node2->next;
      node1->next = node2;
      node2->next = tmp1;
      node1 = tmp1;
      node2 = tmp2;
    }
    return node1;
  }

  void reorderList(ListNode* head) {
    ListNode* middle = findMiddle(head);
    ListNode* reverse = reverseList(middle);
    ListNode* merged = mergeList(head, reverse);
  }
};
Labels: