#53 Coding 面試- LeetCode #143 Reorder List

題目的網址 https://leetcode.com/problems/reorder-list/

這題跟一般的 List 考題一樣，都是把 List element 做順序上的改變．這題的順序改變也比較特別，因為是一前一後一前一後的順序．

一般來說，List 考這種順序排列的考題時，通常都不希望你用到額外的記憶體空間，也就是說所有的動作都要在原來的 List 空間上完成．記得當初在寫這題時，花了不少時間在想要怎麼排出新順序，後來才想到把 List 對折，這樣就變成第一個對到最後一個，第二個對到最後第二個，以此類推，中間的過程也要將成雙成對的配對中把前一對的尾色連到後一對的頭，這樣就完成了．考這種題目真的蠻討論的，因為要很快想到折一半再成雙成對的搭配起來還真不容易．然而，List 的題目就是這樣，只要想法正確了，寫程式就不是問題了．

	public void ReorderList(ListNode head)
	{
	if (head == null) return;
	// find middile node
	ListNode middle = head;
	ListNode last = head;
	while (last.next != null & amp; & last.next.next != null)
	{
	middle = middle.next;
	last = last.next.next;
	}
	// reverse the second half (from middle to the last)
	ListNode p = middle;
	ListNode c = p.next;
	while (c != null)
	{
	ListNode n = c.next;
	c.next = p;
	p = c;
	c = n;
	}
	// reoder
	ListNode h1 = head;
	int count = 1;
	while (h1 != p)
	{
	if (count % 2 == 1)
	{
	ListNode t = h1.next;
	h1.next = p;
	h1 = t;
	if (h1 == p)
	break;
	}
	else
	{
	ListNode t = p.next;
	p.next = h1;
	p = t;
	if (h1 == p)
	break;
	}
	count++;
	}
	h1.next = null;
	}

view raw LeetCode-143 hosted with ❤ by GitHub

以上的解決，Space complexity 是 O(1) ，而 Time complexity 是 O(n)