嗨客网搜索
旋转链表

描述

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

思路

因为移动 k 个位置,k 有可能比当前链表的长度大,也有可能比当前链表的长度小。如果比当前链表长度大,那么就会执行好圈的旋转。因此要求最终的需要旋转的节点个数,就使用 k % 链表长度。

一开始它的链表结构如下:

25 旋转链表.png

然后我们将它连成一个环,即将 5 的节点指向第一个节点 1。

26 旋转链表.png

当 k 等于 2 的时候,我们就是要将指针移动 链表长度 5 - (2 % 5 ) 个位置:

27 旋转链表.png

我们可以看到,按要求 k = 2 的时候,我们最终的末端节点就是 3。因为它是一个环,所以 3 作为末端节点,那么它的下一个节点 4 就是首节点。

28 旋转链表.png

综上,我们这个题目的核心就是找一个旋转链表的末节点。它和 k 的关系就是链表的长度 - k 的值。

代码具体实现

Java语言实现

class Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null || head.next == null){ return head; } // 构造一个环 ListNode old_tail = head; int n; for(n = 1; old_tail.next != null; n++){ old_tail = old_tail.next; } //将首尾链接起来,变成一个环 old_tail.next = head; //定义一个新的节点头,初始值为 head ListNode new_tail = head; //因为是一个环,所以我们可以取长度 k % n 的模值,将需要移动的环排除掉 int needMoveCount = n - k % n; for (int i = 0; i < needMoveCount - 1; i++){ new_tail = new_tail.next; } //遍历到新的节点的末尾,因为是一个环 ListNode new_head = new_tail.next; new_tail.next = null; return new_head; } }

Go语言实现

func rotateRight(head *ListNode, k int) *ListNode { if head == nil || head.Next == nil { return head } // 构造一个环 var old_tail *ListNode = head n := 0 for n = 1; old_tail.Next != nil; n++ { old_tail = old_tail.Next } //将首尾链接起来,变成一个环 old_tail.Next = head //定义一个新的节点头,初始值为 head var new_tail *ListNode = head //因为是一个环,所以我们可以取长度 k % n 的模值,将需要移动的环排除掉 needMoveCount := n - k % n for i := 0; i < needMoveCount - 1; i++{ new_tail = new_tail.Next } //遍历到新的节点的末尾 var new_head *ListNode = new_tail.Next new_tail.Next = nil return new_head }
嗨客网顶部