LinkedList - 143. Reorder List

143. Reorder List

Given a singly linked list L: L_0→_L_1→…→_L__n-1→_L_n,
reorder it to: L_0→_L__n_→_L_1→_L__n-1→_L_2→_L__n_-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.

思路：

题目意思是给一个链表，然后重新按照一个前一个后的顺序重新排序。题目主要是考链表的操作，比如找到链表的终点，然后翻转链表，然后交换链表的节点，考的就是链表操作基本功。注意找中点的时候，找到的是中点的前一个，才能往下寻找节点。

代码：

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 || head.next == null) return;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy, slow = dummy;

        // 1. find list mid node
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 2. reverse end of part
        ListNode start = slow.next;
        ListNode next = start.next;
        while (next != null) {
            start.next = next.next;
            next.next = slow.next;
            slow.next = next;
            next = start.next;
        }

        // 3. reorder list
        ListNode headPart = head;
        ListNode endPart = slow.next;
        while(headPart != slow) {
            slow.next = endPart.next;
            endPart.next = headPart.next;
            headPart.next = endPart;

            headPart = endPart.next;
            endPart = slow.next;
        }
    }
}