题目：

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}.

链接： 

题解：

链表重排序。 可以分为三个步骤，找中点， reverse中点及以后部分，合并链表。

Time Complexity - O(n)， Space Complexity - O(1)。

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public void reorderList(ListNode head) {            // find mid, reverse mid.next to get tail        if(head == null || head.next == null)            return;        ListNode mid = findMid(head);        ListNode tail = reverse(mid.next);        mid.next = null;                ListNode dummy = new ListNode(-1);        ListNode node = dummy;        boolean flag = true;                while(head != null && tail != null) {            if(flag) {                node.next = head;                head = head.next;            } else {                node.next = tail;                tail = tail.next;            }            flag = !flag;            node = node.next;        }                if(head == null)            node.next = tail;        else            node.next = head;        head = dummy.next;    }        private ListNode findMid(ListNode head) {        //find mid of         if(head == null || head.next == null)            return head;        ListNode fast = head, slow = head;                while(fast.next != null && fast.next.next != null) {            fast = fast.next.next;            slow = slow.next;        }                return slow;    }        private ListNode reverse(ListNode head) {        if(head == null || head.next == null)            return head;        ListNode dummy = new ListNode(-1);                while(head != null) {            ListNode temp = head.next;            head.next = dummy.next;            dummy.next = head;            head = temp;        }                return dummy.next;    }}

 

二刷:

一刷写得比较糙，对于各个边界也没算得太清楚。这道题跟 234. Palindrome Linekd List基本一个做法。

1. 找中点
2. reverse后半段
3. 合并前后两段list

这里findMid()以及reverse()两个方法都可以其他类似的linkedlist问题中复用。 要注意的是，找中点时我们不用新建一个dummy节点。最后返回的slow节点，假如链表为奇数长的话，那就是最中间的节点，假如为偶数长的话， 正好是中间两个节点中靠左边的一个。在做这种题的时候，要注意什么时候需要创建一个表头的reference，什么时候不用。要多多练习才能写得简洁。 

Java:

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public void reorderList(ListNode head) {        if (head == null || head.next == null) return;        ListNode mid = findMid(head);        ListNode backPart = reverse(mid.next);        mid.next = null;        ListNode dummy = new ListNode(-1);        ListNode node = dummy;        while (head != null && backPart != null) {            node.next = head;            head = head.next;            node = node.next;            node.next = backPart;            backPart = backPart.next;            node = node.next;        }        if (head != null) node.next = head;        head = dummy.next;    }        private ListNode findMid(ListNode head) {        ListNode fast = head, slow = head;        while (fast != null && fast.next != null) {            fast = fast.next.next;            slow = slow.next;        }        return slow;    }        private ListNode reverse(ListNode head) {        ListNode dummy = new ListNode(-1);        ListNode next = null;        while (head != null) {            next = head.next;            head.next = dummy.next;            dummy.next = head;            head = next;        }        return dummy.next;    }}

 

三刷:

依然不简洁，但是发现了之前代码里的一些小问题。改写了找中点的程序，变成了找中点之前那个点的。这样经过reverse之后，原链表分割出来的左边部分和右边部分就不会有overlap了，并且左边的部分长度总是小于等于右边的部分。最后再merge一下就可以了。

有空也要改写一下243题。

Java:

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public void reorderList(ListNode head) {        if (head == null || head.next == null) return;        ListNode prevMid = getPreMid(head);        ListNode mid = prevMid.next;        prevMid.next = null;        ListNode reversedTail = reverse(mid);                ListNode left = head, right = reversedTail;        ListNode tmp = null;                while (left.next != null) {            tmp = left.next;            left.next = right;            right = right.next;            left = left.next;            left.next = tmp;            left = left.next;        }        left.next = right;    }        private ListNode getPreMid(ListNode head) {        ListNode fast = head, slow = head, prev = head;        while (fast != null && fast.next != null) {            prev = slow;            fast = fast.next.next;            slow = slow.next;        }        return prev;    }        private ListNode reverse(ListNode head) {        ListNode dummy = new ListNode(-1);        ListNode tmp = null;        while (head != null) {            tmp = head.next;            head.next = dummy.next;            dummy.next = head;            head = tmp;        }        return dummy.next;    }}

 

Reference：

https://leetcode.com/discuss/236/does-this-problem-solution-time-complexity-space-comlexity

https://leetcode.com/discuss/21992/a-concise-o-n-time-o-1-in-place-solution

https://leetcode.com/discuss/35599/java-solution-with-3-steps

https://leetcode.com/discuss/44360/java-solution-with-3-steps

http://www.cnblogs.com/yrbbest/p/5002340.html