Given a singly linked list L: L0→L1→…→Ln-1→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,

Given {1,2,3,4}, reorder it to {1,4,2,3}.

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 */

【题意】

给定一个链表，把最后一个结点插入到第1个结点后，倒数第二个结点插入到第2个结点后，倒数第三个结点插入到第3个结点后，以此类推……

【思路】

由题意知。后面 (n-1)/2 个结点须要分别插入到前面 (n-1)/2 个结点后。

那么先把链表分为两段。前面 n-(n-1)/2 个结点为被插入链表，和后面 (n-1)/2 个结点为插入链表。

在插入之前，需先把插入链表逆序。即第n个结点->第n-1个结点->...

【Java代码】

public class Solution {

    public void reorderList(ListNode head) {

        ListNode node = head;

        int cnt = 0;

        while (node != null) {

            cnt++;

            node = node.next;

        }

        if (cnt < 3) return;//3个以下的结点不须要移动

        int k = (cnt - 1) / 2;//须要移动的后k个结点

        int i = 1;

        node = head;

        while (i++ < cnt - k) {

            node = node.next;

        }

        ListNode begin = node.next;//用begin表示须要移动的后k个结点的開始

        node.next = null;//把不须要移动的部分结尾设为null

        //把须要移动的k个结点逆序

        ListNode pre = begin;

        ListNode cur = begin.next;

        begin.next = null;

        while (cur != null) {

            ListNode next = cur.next;

            cur.next = pre;

            begin = cur;

            pre = cur;

            cur = next;

        }

        ListNode node1 = head;

        ListNode node2 = begin;

        while (node1 != null && node2 != null) {

            pre = node1;

            cur = node2;

            node1 = node1.next;//这两行一定要放在以下两行之前。由于pre和node1指向同一个结点，以下操作会改变node1的next；cur和node2同理

            node2 = node2.next;

            cur.next = pre.next;//这两行代码是把cur插入到pre后

            pre.next = cur;

        }

    }

}

【感受】

代码写起来超恶心，写着写着就混乱了。一会儿就不知道next指的是哪个结点了。

【升级版】

先用快慢指针找到链表的中点。然后翻转链表后半部分，再和前半部分组合。

须要注意的是把链表分成两半时，前半段的尾节点要置为NULL，翻转链表时也要把尾节点置为NULL。

public class Solution {

    public void reorderList(ListNode head) {

        if (head == null || head.next == null) return;

        //把整个链表划分成2个等长的子链表。假设原链表长度为奇数。那么第一个子链表的长度多1

        ListNode slow = head, fast = head;

        while (fast.next != null) {

            fast = fast.next;

            if (fast.next != null) fast = fast.next;

            else break;

            slow = slow.next;

        }

        ListNode head1 = head, head2 = slow.next;

        slow.next = null;

        //翻转第二个子链表

        ListNode cur = head2, post = cur.next;

        cur.next = null;

        while (post != null) {

            ListNode tmp = post.next;

            post.next = cur;

            cur = post;

            post = tmp;

        }

        head2 = cur;

        //将两个子链表合并

        ListNode node1 = head1, node2 = head2;

        while (node2 != null) {

            ListNode tmp1 = node1.next;

            ListNode tmp2 = node2.next;

            node1.next = node2;

            node2.next = tmp1;

            node1 = tmp1;

            node2 = tmp2;

        }

    }

}