(Leetcode 143 )Reorder List

题目：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}.

解法思想：

这个没什么好说的，简单说一下：

1. 用快慢指针找到链表的中间节点，并且返回中间节点
2. 从中间节点将链表拆分为两个链表，注意如果链表个数是偶数，那么两个链表长度相等；如果链表个数为奇数，那么后面那半部分组成的链表个数比前面个数多一个。（这个是我cutTwo函数里面这样写成的）
3. 将最后那条链表反转（反转其实有两种方法，第一种是正常的设置三个指针来反转，第二张是另外设置一个dummy头结点，将原来得链表按照头插法插入dummy链表中，就反转了，最后返回dummy.next）
4. 将两条链表合并

每一部分为了清晰，我都独立写成了一个函数。

public class Solution {
    public void reorderList(ListNode head) {
		if( head == null || head.next == null ){
			return;
		}
        ListNode head1 = null, head2 = null;
        head1 = head;
        head2 = cutTwo( head );
        head2 = reverse( head2 );
        head1 = merge(head1, head2);
    }
	
	public ListNode merge( ListNode head1, ListNode head2 ){
		ListNode p = head1, q = head2;
		while( p.next != null ){  //因为head2链表比head1长，所以不用判断head2
			ListNode r = q.next;
			
			q.next = p.next;
			p.next = q;
			
			p = q.next;
			q = r;
		}
		//最后再加上head2 的后半段
		p.next = q;
		return head1;
	}
	
	public ListNode cutTwo( ListNode head ){
		if( head == null || head.next == null ){
			return null;
		}
		ListNode dummy = new ListNode(-1);
		dummy.next = head;
		//p 是慢指针，q是快指针
		ListNode pre = dummy, p = head,q = head;  
		while( p != null && q != null && q.next != null ){
			pre = p;
			p = p.next;
			q = q.next.next;
		}
		pre.next = null;    //一定要记得将第一条链表的尾next最后设置为null
		return p;
	}
	
	public ListNode reverse( ListNode head ){
		if( head == null || head.next == null ){
			return head;
		}
		ListNode p = head, q = head.next;
		while( q != null ){
			ListNode r = q.next;
			q.next = p;
			
			p = q;
			q = r;
		}
		head.next = null;
		return p;
	}
}