2021-03-27：給你一個(gè)鏈表的頭節(jié)點(diǎn) head ，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置。輸入：head = 1→2→3→4→5, k = 2，輸出：4→5→1→2→3。
福大大 答案2020-03-27：
1.找尾節(jié)點(diǎn)并且計(jì)算鏈表節(jié)點(diǎn)個(gè)數(shù)。
2.如果k大于等鏈表節(jié)點(diǎn)個(gè)數(shù)，需要取模，k一定在[0,節(jié)點(diǎn)個(gè)數(shù))范圍之內(nèi)。如果k=0，直接返回頭節(jié)點(diǎn)。
3.求倒數(shù)k+1的節(jié)點(diǎn)。
4.緩存倒數(shù)第k節(jié)點(diǎn)ans。
5.尾節(jié)點(diǎn)連頭節(jié)點(diǎn)。
6.倒數(shù)k+1節(jié)點(diǎn)的Next指針為空。
7.返回ans。
代碼用golang編寫(xiě)，代碼如下：
package main
import "fmt"
func main() {
head := &ListNode{Val: 1}
head.Next = &ListNode{Val: 2}
head.Next.Next = &ListNode{Val: 3}
head.Next.Next.Next = &ListNode{Val: 4}
printlnLinkNodeList(head)
k := 6
fmt.Println("k =", k)
fmt.Println("----------------")
ret := rotateRight(head, k)
printlnLinkNodeList(ret)
}
type ListNode struct {
Val int
Next *ListNode
}
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
//找尾節(jié)點(diǎn)并且計(jì)數(shù)
cnt := 1
tail := head
for tail.Next != nil {
cnt++
tail = tail.Next
}
k = k % cnt
if k == 0 { //剛好是頭節(jié)點(diǎn)，就不用操作了。
return head
}
//找倒數(shù)第k+1節(jié)點(diǎn)
fast := head
slow := head
k++
for k > 0 {
fast = fast.Next
k--
}
for fast != nil {
fast = fast.Next
slow = slow.Next
}
//緩存結(jié)果
ans := slow.Next
//尾節(jié)點(diǎn)連頭節(jié)點(diǎn)
tail.Next = head
//倒數(shù)k+1節(jié)點(diǎn)無(wú)Next指針
slow.Next = nil
return ans
}
//鏈表打印
func printlnLinkNodeList(head *ListNode) {
cur := head
for cur != nil {
fmt.Print(cur.Val, "\t")
cur = cur.Next
}
fmt.Println()
}
執(zhí)行結(jié)果如下：
在這里插入圖片描述
