25. Reverse Nodes in k-Group
https://leetcode.com/problems/reverse-nodes-in-k-group/
題意
有一個 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 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。