143. Reorder List

Link

Solution

這題跟上題概念類似，也是先把list分成左右兩個。

reserve右邊的 ，然後merge起來

值得注意的點是reverse時，其實左右list仍有指標相連。必須把連線斷掉才行，否則會有cycle erorr。

我是在做完之後把fast.next設成null，避免他連到slow的最前面的元素導致cycle。

這題要考慮 偶數個node跟奇數node的情況，奇數node的情況下 要reverse的 head要往下一個node移動一次 :

        if(fast != null){ //奇數node
            slow = slow.next;
        }

 public void reorderList(ListNode head) {
        if(head == null) return ;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast != null){
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;
        while(slow != null){
            ListNode next = fast.next;
            ListNode slowIndex = slow.next;
            slow.next = fast.next;
            fast.next = slow;
            slow = slowIndex;
            fast = next;
        }
        //have to set the fast.next to null pointer 
        //since it might connect to slow originally
        fast.next = null;
    }
    
    public ListNode reverse(ListNode node){
        ListNode prev = null;
        while(node != null){
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }
        return prev;
    }