剑指 Offer II 026. 重排链表

迭代法

1. 将链表拆平均拆分成两部分，再返回第二部分链表，然后将两部分链表交替合并。
2. 交替合并比较考验细节，确定以第一个链表为主链表，第二个链表为辅链表即可。

3. 找中点时需要完成断链操作 ```java class Solution { public void reorderList(ListNode head) {

    if (head == null || head.next == null) return ;
    // first: get Mid Node
    ListNode midNode = getMidNode(head);
    // second: reverse newHead
    ListNode n2 = reverse(midNode);
    // third: merge
    merge(head, n2);

   }

   // 交替 private void merge(ListNode n1, ListNode n2) {

    ListNode dummy = new ListNode(0);
    while (n1 != null && n2 != null) {
        ListNode n1Next = n1.next;
        ListNode n2Next = n2.next;
   
        n1.next = n2;
        n1 = n1Next;
   
        n2.next = n1Next;
        n2 = n2Next;
    }
   

   }

   private ListNode reverse(ListNode node) {

    ListNode prev = null, p = node;
    while (p != null) {
        ListNode next = p.next;
        p.next = prev;
        prev = p;
        p = next;
    }
    return prev;
   

   }

// 获取中心节点
private ListNode getMidNode(ListNode head) {
    if (head == null) return null;
    // use slow and fast pointer
    ListNode fast = head, slow = head;
    while (fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    ListNode newHead = slow.next;
    slow.next = null;
    return newHead;
}

}

<a name="S2I0U"></a>
## 递归法

```java
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return ;
        reorderList(head, len(head));
    }

    private ListNode reorderList(ListNode head, int len) {
        if (len == 0) return null;
        if (len == 1) return head;
        if (len == 2) return head.next;

        ListNode tail = reorderList(head.next, len - 2);
        ListNode temp = tail.next;
        tail.next = tail.next.next;
        temp.next = head.next;
        head.next = temp;
        return tail;
    }

    private int len(ListNode head) {
        ListNode p = head;
        int count = 0;
        while (p != null) {
            count++;
            p = p.next;
        }
        return count;
    }
}