25. Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/
Hard
Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.
You may not alter the values in the list's nodes, only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]
Example 2:
Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]
Constraints:
- The number of nodes in the list is
n. 1 <= k <= n <= 50000 <= Node.val <= 1000
Follow-up: Can you solve the problem in O(1) extra memory space?
題意
有一個 Linked List ，將 k 個節點為一組，並且將這一組內部的元素進行反轉，如果節點總數不足 k 個就不用反轉，最後回傳反轉後的結果。
解題思路
- 依每 k 個元素進行分組，並且順便找出結尾的元素。
- 將這個組的內部元素進行反轉。
- 更新這個組的 head 與 tail 元素。
原始碼
func reverseKGroup(head *ListNode, k int) *ListNode {
// 1. grouping and find head and tail of group
// 2. reverse this group
// 3. update head and tail
sentinal := &ListNode{}
last := sentinal
for head != nil {
// 1. grouping and find head and tail of group
end := findEnd(head, k)
if end == nil {
break
}
nextGroupHead := end.Next
// 2. reverse this group
reverseLinkedList(head, nextGroupHead)
// 3. update head and tail
last.Next = end
head.Next = nextGroupHead
last = head
head = nextGroupHead
}
return sentinal.Next
}
func findEnd(head *ListNode, k int) *ListNode {
for head != nil {
k--
if k == 0 {
return head
}
head = head.Next
}
return nil
}
func reverseLinkedList(head, tail *ListNode) {
last := head
head = head.Next
for head != tail {
headNext := head.Next
head.Next = last
last = head
head = headNext
}
}
結尾
你有更好或更簡單的解決方案嗎？
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。
