題目描述
給出一個(gè)鏈表澳窑，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)钠怯，并返回翻轉(zhuǎn)后的鏈表恋追。
k 是一個(gè)正整數(shù)凭迹，它的值小于或等于鏈表的長(zhǎng)度颅崩。如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么將最后剩余節(jié)點(diǎn)保持原有順序蕊苗。
示例:
給定這個(gè)鏈表：1->2->3->4->5
當(dāng) k = 2 時(shí)，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時(shí)沿彭，應(yīng)當(dāng)返回: 3->2->1->4->5
說明:
- 你的算法只能使用常數(shù)的額外空間朽砰。
- 你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換喉刘。
解題思路
1. 取鏈表的前K個(gè)節(jié)點(diǎn)瞧柔，如果夠K個(gè)節(jié)點(diǎn)，就截?cái)嗪筮M(jìn)行反轉(zhuǎn)睦裳，不夠K個(gè)節(jié)點(diǎn)造锅，說明處理完了，return
2. 反轉(zhuǎn)完前K個(gè)節(jié)點(diǎn)后廉邑，使用遞歸哥蔚，處理后面的鏈表
代碼實(shí)現(xiàn)
// ListNode Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func reverseKGroup(head *ListNode, k int) *ListNode {
if k < 2 || head == nil || head.Next == nil {
return head
}
tail, needReverse := getTail(head, k)
if needReverse {
tailNext := tail.Next
//斬?cái)?tail 后的鏈接
tail.Next = nil
head, tail = reverse(head, tail)
//tail 后面接上尾部的遞歸處理
tail.Next = reverseKGroup(tailNext, k)
}
return head
}
func getTail(head *ListNode, k int) (*ListNode, bool) {
for k > 1 && head != nil {
head = head.Next
k--
}
return head, k == 1 && head != nil
}
func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
//反轉(zhuǎn)鏈表
prev, cur := head, head.Next
for cur != nil {
prev, cur, cur.Next = cur, cur.Next, prev
}
return tail, head
}
GitHub
- 源碼傳送門
- 項(xiàng)目中會(huì)提供各種數(shù)據(jù)結(jié)構(gòu)及算法的Golang實(shí)現(xiàn), LeetCode解題思路及答案
