链表洗牌

package 链表下;

public class reorderList {
	public static int lengthOfList(ListNode head) {
		ListNode p = head;
		int n = 0;
		while (p != null) {
			p = p.next;
			n++;
		}
		return n;
	}

	public static ListNode reverseList(ListNode head) {
		ListNode pre = head;
		ListNode p = pre.next;
		ListNode next;
		while (p != null) {
			next = p.next;
			p.next = pre;
			pre = p;
			p = next;
		}
		head.next = null;
		return pre;
	}

	public static void reorderList(ListNode head) {
		int n = lengthOfList(head);
		int half = n / 2;
		if (n % 2 != 0) {
			half++;
		}
		ListNode leftEnd = head;
		for (int i = 1; i < half; i++) {
			leftEnd = leftEnd.next; // 左半边链表的尾节点
		}
		ListNode rightStart = leftEnd.next; // 右半边链表的开始节点
		rightStart = reverseList(rightStart);// 反转右边的节点，为洗牌做准备
		leftEnd.next = null;
		ListNode left = head;
		ListNode right = rightStart;
		boolean flag = true;
		ListNode next = null;
		while (right != null) {
			if (flag) {
				next = left.next;
				left.next = right;
				left = next;
			} else {
				next = right.next;
				right.next = left;
				right = next;
			}
			flag = !flag;
		}
	}

	public static void main(String[] args) {
		int[] array = { 1, 2, 3, 4, 5, 6 };
		ListNode head = ListNode.arrayToList(array);
		reorderList(head);
		ListNode.printList(head);
	}
}