> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linked-list/reorder-list.md).

# Reorder List

Given a singly linked list *L*: *L*0→*L*1→…→*Ln*-1→*L*n,\
reorder it to: *L*0→*Ln*→*L*1→*Ln*-1→*L*2→*Ln*-2→…

You may **not** modify the values in the list's nodes, only nodes itself may be changed.

**Example 1:**

```
Given 1->2->3->4, reorder it to 1->4->2->3.
```

**Example 2:**

```
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.
```

先找中点，把原来的list拆为两个，把后半截reverse，然后再把两个list一个一个交替连起来

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null){
            return;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        //find mid point;
        ListNode slow = dummy,fast = dummy;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //slow now is mid point;
        
        //got the second half head;
        ListNode head2 = reverse(slow);
        
        slow.next = null;
        
        connect(dummy.next,head2);
        
        
    }
    
    public ListNode connect(ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(-1);
        dummy.next = head1;
        
        ListNode tail = dummy;
        
        while(head1 != null && head2 != null){
            tail.next = head1;
            tail = head1;
            head1 = tail.next;
            tail.next = head2;
            tail = head2;
            head2 = tail.next;
        }
        
        if(head1 != null){
            tail.next = head1;
        }
        
        if(head2 != null){
            tail.next = head2;
        }
                
        return dummy.next;
    }
    
    public ListNode reverse(ListNode node){
        if(node == null || node.next == null){
            return null;
        }
        
        ListNode cur = node.next;
        ListNode pre = null, next = null;
        
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
    
    
    
}
```