leetcode: Reorder List

问题描述：

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

原问题链接：https://leetcode.com/problems/reorder-list/

 

问题分析

　　在写具体的代码实现之前，我们先看问题的要求。它要求是将如L0, L1, L2...Ln的链表变成L0, Ln, L1, Ln-1...。这种样式相当于将链表从正中间拆分成两截。对于后面的那一截先反转一下。然后再将这两截链表按照顺序依次的加入元素，构成一个新的链表。

　　只要找到这个规律，后面的实现就有思路了。我们首先找到链表中间节点，因为要从它开始划分成两截。从实现的角度来说，我们可以用快慢指针的方式。当快指针到达链表末尾的时候，慢指针所在的位置就是分割点。在得到这个分割点之后，我们再将后面的这部分反转。关于反转的具体实现可以参考之前的讨论。

　　在反转完成之后，剩下的就是要考虑怎么实现两个链表的合并了。因为这里是轮流加入元素合并。我们的详细实现可以参照如下图的流程：

　　一开始，我们有两个链表first, second，我们额外声明一个变量next：

　　　在下一步的时候，我们实现元素的交叠：

 

 

　　它的作用相当于实现second.next = first.next; first.next = second;　然后我们再确定下一步first, second的位置：

　　

　　这种调整相当于如下的代码：first = second.next; second = next;　这样，我们就完成了一个元素交叠的过程。我们通过循环上述的过程就可以实现最终的交叠。

　　结合上述的讨论，详细的代码实现如下： 

 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null) return;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode first = head;
        ListNode half = slow.next;
        slow.next = null;
        half = reverse(half);
        while(first != null && half != null) {
            ListNode next = half.next;
            half.next = first.next;
            first.next = half;
            first = half.next;
            half = next;
        }
    }
    
    private ListNode reverse(ListNode node) {
        ListNode tmp = null, pre = null;
        while(node != null) {
            tmp = node;
            node = node.next;
            tmp.next = pre;
            pre = tmp;
        }
        return tmp;
    }
}