[LeetCode] 143. Reorder List

轉自LeetCode

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}.

<Solution>
這題一開始想到的方式是用 recursive 來解，但會 TLE，必須用其它想法

想法如下

• 利用快慢指針，找到 list 的中間點，然後斷開，形成前後兩個 list

• 將後半段的 list 做反轉

• 將反轉後的 list，間隔地插入前半段的 list

code 如下(參考資料)

c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	void reorderList(ListNode* head) {
	if(!head || !head->next || !head->next->next) {
	return;
	}
	ListNode *slow = head;
	ListNode *fast = head;
	//>> find the mid point of the list
	while(fast->next && fast->next->next) {
	slow = slow->next;
	fast = fast->next->next;
	}
	ListNode *reverseTail = slow->next;
	slow->next = NULL;
	ListNode *reverseHead = NULL;
	//>> reverse the nodes after mid point
	while(reverseTail) {
	ListNode *tmpN = reverseTail->next;
	reverseTail->next = reverseHead;
	reverseHead = reverseTail;
	reverseTail = tmpN;
	}
	//>> insert reverse list into front half of the list
	while(head && reverseHead) {
	ListNode *nextNode = head->next;
	ListNode *nextReverseNode = reverseHead->next;
	head->next = reverseHead;
	reverseHead->next = nextNode;
	head = nextNode;
	reverseHead = nextReverseNode;
	}
	}
	};

view raw reorderLinkedList.cpp hosted with ❤ by GitHub

還有一種解法

可以先將 node 都放到一個 stack，這樣也會知道整個 list 的長度

然後只需要將 (stack.size - 1) / 2 個 node 從 stack 拿出來，按照題目要求重新接上 list 即可

因為是用 stack ，所以也達到從後面的 node 反轉的效果

Kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun reorderList(head: ListNode?): Unit {
	var curr = head
	val stack = mutableListOf<ListNode>()
	while(curr != null) {
	stack.add(curr!!)
	curr = curr!!.next
	}
	var limit = (stack.size - 1) / 2
	curr = head
	var node: ListNode
	while(limit > 0) {
	node = stack.last()
	stack.removeAt(stack.lastIndex)
	node.next = curr!!.next
	curr!!.next = node
	curr = node.next
	--limit
	}
	stack.last().next = null
	}
	}

view raw reorder_list.kt hosted with ❤ by GitHub