# 143. Reorder List

[Link](https://leetcode.com/problems/reorder-list/)

**Solution**

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

reserve右邊的 ，然後merge起來

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

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

![](https://2628390332-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M0RnkuvOeqe0clAIN1b%2F-M5KVCfUTUmjkuUni3G3%2F-M5Krl4-nIZ93cy0z0tB%2Fimage.png?alt=media\&token=6e6c87df-6b54-4ce5-8e2e-a347fa1e7a66)

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

```
        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;
    }
```
