给定一个单链表 L：L0→L1→…→Ln-1→Ln ，

 

将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

答案：

 1public void reorderList(ListNode head) {
 2    if (head == null || head.next == null) return;
 3    //找到链表中间的节点
 4    ListNode p1 = head;
 5    ListNode p2 = head;
 6    while (p2.next != null && p2.next.next != null) {
 7        p1 = p1.next;
 8        p2 = p2.next.next;
 9    }
10    //把后半部分的链表进行翻转 1->2->3->4->5->6 to 1->2->3->6->5->4
11    ListNode preMiddle = p1;
12    ListNode preCurrent = p1.next;
13    while (preCurrent.next != null) {
14        ListNode current = preCurrent.next;
15        preCurrent.next = current.next;
16        current.next = preMiddle.next;
17        preMiddle.next = current;
18    }
19    //然后前半部分和后半部分交替连接 1->2->3->6->5->4 to 1->6->2->5->3->4
20    p1 = head;
21    p2 = preMiddle.next;
22    while (p1 != preMiddle) {
23        preMiddle.next = p2.next;
24        p2.next = p1.next;
25        p1.next = p2;
26        p1 = p2.next;
27        p2 = preMiddle.next;
28    }
29}

解析：

这题理解起来不难，其中第11行到18行是链表的翻转，关于链表的翻转其实解法也比较多，如果不太明白，还可以看一下157，反转链表，下面再来看一种解法

 1public void reorderList(ListNode head) {
 2    if (head == null || head.next == null)
 3        return;
 4    Deque<ListNode> stack = new ArrayDeque<>();
 5    ListNode ptr = head;
 6    while (ptr != null) {
 7        stack.push(ptr);
 8        ptr = ptr.next;
 9    }
10    int cnt = (stack.size() - 1) / 2;
11    ptr = head;
12    while (cnt-- > 0) {
13        ListNode top = stack.pop();
14        ListNode tmp = ptr.next;
15        ptr.next = top;
16        top.next = tmp;
17        ptr = tmp;
18    }
19    stack.pop().next = null;
20}

这个先把链表节点都存放在双端队列中，这里面相当于压栈，代码也很好理解，我们只要看最后第19行，他表示的是这个最后pop的节点是新链表的尾结点，所以他的next要必须置为null。我们再来看最后一种，递归的解法

 1public void reorderList(ListNode head) {
 2    reorderList(head, getLength(head));
 3}
 4
 5ListNode reorderList(ListNode head, int len) {
 6    if (len == 0)
 7        return null;
 8    if (len == 1)
 9        return head;
10    if (len == 2)
11        return head.next;
12    ListNode tail = reorderList(head.next, len - 2);
13    ListNode tmp = tail.next;
14    tail.next = tail.next.next;
15    tmp.next = head.next;
16    head.next = tmp;
17    return tail;
18}
19
20int getLength(ListNode head) {
21    int len = 0;
22    while (head != null) {
23        ++len;
24        head = head.next;
25    }
26    return len;
27}