未分類

Reorder List

Go, LeetCode, LinkedList

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:

1
Given {1,2,3,4}, reorder it to {1,4,2,3}.
提示 解題應用
LinkedList Pointer

Default:

1
2
3
4
5
6
7
8
9
10
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
}

解答思路:

這題只要仔細觀查數列的規律，我想就可以很輕易的將題目解開，以[1,2,3,4,5,6,7,8,9]來說:

1
2
原始LinkedList: [1,2,3,4,5,6,7,8,9]
結果LinkedList: [1,9,2,8,3,7,4,6,5]

如果將結果LinkedList分段來看的話

1
2
結果LinkedList(奇): [1, ,2, ,3, ,4, ,5]
結果LinkedList(偶): [ ,9, ,8, ,7, ,6, ]

我們可以發現結果LinkedList奇數位置的值正好是原始LinkedList開頭到中間的值(如果LinkedList的節點數是偶數，以中間偏前面的節點為主)，而結果LinkedList偶數位置的值則是中間到後頭值的顛倒，剩下的只要知道怎麼找出”LinkedList的中間節點”與”顛倒中間到後頭LinkedList的節點”就只要嫁接就好，這兩個技巧的實作可以參考Palindrome Linked List。

程式碼解說:

透過規律可得知結果LinkedList奇數的位置是開頭到中間節點的值，所以一開始就透過慢、快的速度(1:2)同時遍歷以找出中間的節點(結束後位於slow的位置上)，接著如果slow不為空就將該節點後頭的LinkedList做翻轉(也就是中間到後頭的LinkedList)，並再將該節點的下一個位置改為nil，如此一來就可以得到兩條LinkedList，一條是原LinkedList的開頭到中間節點，另一條則是原LinkedList的結尾到中間節點，最後就是在這兩條LinkedList的節點之間彼此來回嫁接直到全數節點嫁接完為止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func reorderList(head *ListNode)  {
    var tmp *ListNode
    var fast *ListNode
    var reverse *ListNode
    slow := head
    if head != nil {
        fast = head.Next
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    if slow != nil {
        reverse = reverseList(slow.Next)
        slow.Next = nil
    }
    for head != nil {
        tmp = head
        head = head.Next
        tmp.Next = reverse
        if reverse != nil {
            tmp = reverse
            reverse = reverse.Next
            tmp.Next = head
        }
    }
}

顛倒LinkedList節點的實作則是直接之前的文章: Reverse Linked List，詳細的節說可以到該處查看

1
2
3
4
5
6
7
8
9
10
11
func reverseList(node *ListNode) *ListNode {
	var flag *ListNode
	var preNode *ListNode
	for node != nil {
		flag = node
		node = node.Next
		flag.Next = preNode
		preNode = flag
	}
	return flag
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
func reorderList(head *ListNode)  {
    var tmp *ListNode
    var fast *ListNode
    var reverse *ListNode
    slow := head
    if head != nil {
        fast = head.Next
    }
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    if slow != nil {
        reverse = reverseList(slow.Next)
        slow.Next = nil
    }
    for head != nil {
        tmp = head
        head = head.Next
        tmp.Next = reverse
        if reverse != nil {
            tmp = reverse
            reverse = reverse.Next
            tmp.Next = head
        }
    }
}
func reverseList(node *ListNode) *ListNode {
	var flag *ListNode
	var preNode *ListNode
	for node != nil {
		flag = node
		node = node.Next
		flag.Next = preNode
		preNode = flag
	}
	return flag
}

總結:

要將LinkedList:L0→L1→…→Ln-1→Ln排序成L0→Ln→L1→Ln-1→L2→Ln-2→…，透過仔細觀查規律會發現奇數位置的值正好是原始LinkedList開頭到中間的值，偶數位置的值則是中間到後頭值的顛倒，剩下的只要知道怎麼找出”LinkedList的中間節點”與”顛倒中間到後頭LinkedList的節點”就只要嫁接就好。

分享到