20241111，LeetCode 每日一题，用 Go 实现旋转链表

题目

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

解题思路

1. 计算链表长度：遍历链表来获取链表的长度 n，因为链表的旋转其实是循环移动，所以将 k 对 n 取模 k = k % n，这样可以减少不必要的旋转次数。

2. 判断边界情况：如果 k 为 0 或 n 小于等于 1，则无需旋转，直接返回原链表。

3. 找到新链表的尾节点：旋转后的链表可以看作是从倒数第 k 个节点断开，将链表末尾连接到头部形成一个环，再在新的断点处截断形成新的链表。

   • 找到新链表的尾节点，即原链表的第 n - k 个节点，将它的 next 指向 null。

4. 返回新链表头节点：此时新链表的头节点是第 n - k + 1 个节点。

这样通过一次遍历获取长度，再一次遍历找到断点，时间复杂度为 O(n)。

代码

func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || head.Next == nil || k == 0 {
return head
}
n := 1
tail := head
for tail.Next != nil {
tail = tail.Next
length++
}

k %= n
if k == 0 {
return head
}
tail.Next = head
newTail := head
for i := 0; i < n-k-1; i++ {
newTail = newTail.Next
}
newHead := newTail.Next
newTail.Next = nil
return newHead
}

原文地址：https://blog.csdn.net/github_37151951/article/details/143698201

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！