reorder list ---LeetCode

题目描述
将给定的单链表L： L 0→L 1→…→L n-1→L n,
重新排序为： L 0→L n →L 1→L n-1→L 2→L n-2→…
要求使用原地算法，并且不改变节点的值
例如：
对于给定的单链表{1,2,3,4}，将其重新排序为{1,4,2,3}.
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 must do this in-place without altering the nodes' values.

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

思路：

1. 将链表从中间断开，分成两个链表: 这里使用快慢指针方法找到中间节点，再断开。
2. 反转第二个链表；
3. 将第二个链表一次插入到第一个链表

//找到中间节点,进行断链
//
import java.util.*;
public class Solution {
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null)
            return ;
        //快慢指针，找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode start = head;
        ListNode end = mid.next;
        mid.next = null;//断链
        //翻转end链表,处理第一个节点
        ListNode pre = end;
        ListNode cur = pre.next;
        while(cur !=null){
            if(pre == end)
                pre.next = null;
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        end = pre;
        //插入
        while(start != null && end!=null){
            ListNode next1 = start.next;
            ListNode next2 = end.next;
            start.next = end;
            end.next = next1;
            start = next1;
            end = next2;
        }
        return ;

    }
}