LeetCode | Reorder List

题目

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→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}.

本题思路如下：首先将题目所给单链表从中间分割为两个单链表，再将后半个单链表反向，最后合并两个单链表即可。

代码

public class ReorderList {
	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public void reorderList(ListNode head) {
		if (head == null || head.next == null) {
			return;
		}

		// find the second half head
		ListNode fast = head.next;
		ListNode slow = head;
		while (fast != null && fast.next != null) {
			fast = fast.next.next;
			slow = slow.next;
		}

		// reverse the second half
		ListNode p = slow.next;
		slow.next = null; // cut the first half
		ListNode pPre = null;
		ListNode pSuf = p.next;
		while (p != null) {
			pSuf = p.next;
			p.next = pPre;
			pPre = p;
			p = pSuf;
		}

		// combine two halves
		ListNode l1 = head;
		ListNode l2 = pPre;
		while (l1 != null && l2 != null) {
			ListNode l1Next = l1.next;
			ListNode l2Next = l2.next;
			l1.next = l2;
			l2.next = l1Next;
			l1 = l1Next;
			l2 = l2Next;
		}
	}
}