143. Reorder List

# Medium

Key idea: find middle + reverse latter part + merge

核心：快慢指针找到中间元素 ＋ 反转后半部分 ＋ 插入合并

length of list is even

length of list is odd

• When searching middle node, faster = head.next, slow = head. Pay attention to even or odd cases, which node should be middle node.

• When merging two list, should record head1.next and head2.next respectively before doing insertion.

• The condition of finishing insertion is both of head.next are null.

• 当寻找中间点时，注意list长度是基数还是偶数时，中间点应该是哪个

• 当合并两部分时，应先分别保留两个list的下一个节点，然后再插入元素

• 合并完成的条件是两个list的当前指针的下一个节点都为空

Python example: 注意快慢指针的终止条件，慢指针指向的位置，要把两个list分开

Java

class Solution {
    public void reorderList(ListNode head) {
        // edge case
        if(head == null || head.next == null)
            return;
        
        // slow and fast pointer to find the middle point pre
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // reverse the second part from pre
        ListNode pre = null, curr = slow;
        while(curr != null) {
            ListNode tempNext = curr.next;
            curr.next = pre;
            
            pre = curr;
            curr = tempNext;
        } // pre is the new head of second part
        
        // combine them
        ListNode head1 = head, head2 = pre;
        while(head2.next != null) {
            ListNode next1 = head1.next;
            ListNode next2 = head2.next;
            
            head1.next = head2;
            head2.next = next1;
            
            head1 = next1;
            head2 = next2;
        }
    }
}

Python

T = O(N/2 + N/2) = O(N), S = O(1)