143. Reorder List

leetcode

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

Example 1:

image

Input: head = [1,2,3,4] Output: [1,4,2,3]

Example 2:

image

Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]

Constraints:

  • The number of nodes in the list is in the range [1, 5 * 104].
  • 1 <= Node.val <= 1000
/**
 * 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) {
        // 使用快慢指針尋找中間節點
        // 快指針每次移動兩步，慢指針每次移動一步，當快指針到達鏈表末尾時，慢指針剛好到達中間節點。
        ListNode *slow = head;
        ListNode *fast = head->next;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 將中間節點之後的 linked list 反轉，以便後續可以交錯合併。
        ListNode* cur = slow->next;
        ListNode* prev = nullptr;

        while(cur) {
            ListNode* temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }

        // 斷開前後兩個部分
        slow->next = nullptr;

        // 將前半部分和反轉後的後半部分交錯合併。
        ListNode *first = head;
        second = prev;
        while(second) {
            ListNode* node1 = first->next;
            ListNode* node2 = second->next;
            first->next = second;
            second->next = node1;
            first = node1;
            second = node2;
        }
    }
};
  • T: O(N)O(N)
  • S: O(1)O(1)