未分類

Odd Even Linked List

Go, LeetCode, LinkedList

Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

For example:

1
2
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on …

提示 解題應用
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 oddEvenList(head *ListNode) *ListNode {
}

解答思路:

非常單純的一題，只要以兩個指標分別儲存奇數與偶數的LinkedList，在遍歷原LinkedList的同時一邊將節點作分配，最後待遍歷結束後將偶數的LinkedList接上奇數的LinkedList後頭即可。

程式碼解說:

一開始先初始化用來分別儲存奇數與偶數LinkedList的頭節點，再以兩個指標指向兩串LinkedList的結尾以利後續新增節點，另外也需要一個計數器來分辨節點是奇數還是偶數，接下來就可以用迴圈來將原LinkedList節點一一取出，同時一邊將節點作分配(計數器為奇數的節點接到儲存奇數LinkedList的後頭，反之偶數也是如此)，待遍歷結束後將偶數的LinkedList接上奇數的LinkedList後頭，並記得將偶數LinkedList結尾的下一個節點改為nil以防產生環(cycle)，最後回傳整串LinkedList的開頭，也就是奇數頭節點的下一個節點(原LinkedList的第一個節點)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
odd := &ListNode{}
oddRear := odd
even := &ListNode{}
evenRear := even
count := 1
for head != nil {
	if count%2 != 0 {
		oddRear.Next = head
		oddRear = head
	} else {
		evenRear.Next = head
		evenRear = head
	}
	head = head.Next
	count++
}
oddRear.Next = even.Next
evenRear.Next = nil
return odd.Next

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func oddEvenList(head *ListNode) *ListNode {
	odd := &ListNode{}
	oddRear := odd
	even := &ListNode{}
	evenRear := even
	count := 1
	for head != nil {
		if count%2 != 0 {
			oddRear.Next = head
			oddRear = head
		} else {
			evenRear.Next = head
			evenRear = head
		}
		head = head.Next
		count++
	}
	oddRear.Next = even.Next
	evenRear.Next = nil
	return odd.Next
}

總結:

要將原LinkedList順序改為奇數節點在前面，而偶數節點接在後頭，只要以兩個指標分別儲存奇數與偶數的LinkedList，在遍歷原LinkedList的同時一邊將節點作分配，最後待遍歷結束後將偶數的LinkedList接上奇數的LinkedList後頭即可。

分享到