143. Reorder List

[fockspaces]

https://leetcode.com/problems/reorder-list/description/

[fockspaces]

將每個 node 的 prev 記下來，用回文的方式不斷互指，判斷奇偶決定終止條件 最後將 tail->next = NULL 來完成 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:
    void reorderList(ListNode* head) {
        unordered_map<ListNode*, ListNode*> prev;
        ListNode *tail = head, *cur = head;
        while(tail && tail->next) {
            prev[tail->next] = tail; tail = tail->next;
        }
        while(cur->next != tail && cur != tail) {
            ListNode* next = cur->next;
            cur->next = tail; tail->next = next;
            cur = next; tail = prev[tail];
        }
        tail->next = NULL;
    }
};

[fockspaces]

作法2是先將後半 reverse list，接著將兩 list 互指 （留給之後做）第一個寫法比較精簡