143. Reorder List - Medium

前往題目

想法

• 用hashmap存，每一個對應的數字，然後再一次循環把全部拼起來

思路

意外的好理解，因為都是用到之前寫過的演算法

1. 找到middle node(快慢指針)
2. 把middle之後的，也就是second half反轉
3. 再和first half合併(因為此時second half已經反轉，可以直接接上)

Code

class Solution {
    public void reorderList(ListNode head) {
        ListNode slow = head, fast = head.next;

        // Find the middle
        // slow will be the middle
        // fast will be the last node or the null node after last node
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode second = slow.next; // Second half head
        slow.next = null; // detach first half from second half
        ListNode prev = null; // Previous node
        // Reverse the second half
        while (second != null) {
            // Store original next node
            ListNode tmp = second.next;
            // Reverse the link
            second.next = prev;
            // Move pointers
            prev = second;
            second = tmp;
        }
        // prev becomes the last node of second half
        // second becomes the null node after the last node 

        // Attach first half with reversed second half
        ListNode first = head;
        second = prev;
        while (second != null) {
            // Save original next node
            ListNode tmp1 = first.next, tmp2 = second.next;
            // Link it
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}