Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 143. Reorder List

---

題目：


方法：

1. 找中點(快慢指標)
2. 反轉後半段
3. 合併兩段(交錯)

解答：

/**
 * 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) {
            return;
        }

        ListNode *slow = head;
        ListNode *fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode *pre = nullptr;
        ListNode *cur = slow->next;

        slow->next = nullptr;
        while (cur) {
            ListNode *next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        ListNode *p1 = head;
        ListNode *p2 = pre;
        while (p2) {
            ListNode *n1 = p1->next;
            ListNode *n2 = p2->next;

            p1->next = p2;
            p2->next = n1;

            p1 = n1;
            p2 = n2;
        }
    }
};