当前位置：
  1. 首页
  2. 数据结构与算法
  3. 算法系统课
  4. 正文

LeetCode61. 旋转链表🌟🌟🌟中等

算法系统课 免费

课后作业

问题描述

原文链接：61. 旋转链表

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

示例 1：

img

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

img

输入：head = [0,1,2], k = 4
输出：[2,0,1]

提示：

  • 链表中节点的数目在范围 [0, 500] 内
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 109

代码实现

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        int n = 1;
        ListNode temp = head;
        while(temp.next != null){
            n++;
            temp = temp.next;
        }
        k = k % n;
        if(k - n == 0){
            return head;
        }
        temp.next = head;
         //定位到第 n - k 个节点，然后拆开。
         for(int i = 1; i < n - k; i++){
             head = head.next;
         }
        ListNode newHead = head.next;
        // 拆开环
        head.next = null;

        return newHead;

    }
}

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        n = 1
        temp = head
        while temp.next != None:
            n += 1
            temp = temp.next
        k = k % n
        if k - n == 0:
            return head
        temp.next = head
        #定位到第 n - k 个节点，然后拆开。
        for i in range(1, n - k):
            head = head.next
        newHead = head.next
        # 拆开环
        head.next = None
        return newHead

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head == nullptr || head->next == nullptr){
            return head;
        }
        int n = 1;
        ListNode* temp = head;
        while(temp->next != nullptr){
            n++;
            temp = temp->next;
        }
        k = k % n;
        if(k - n == 0){
            return head;
        }
        temp->next = head;
         //定位到第 n - k 个节点，然后拆开。
         for(int i = 1; i < n - k; i++){
             head = head->next;
         }
        ListNode* newHead = head->next;
        // 拆开环
        head->next = nullptr;

        return newHead;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    //计算链表长度
    n := 1
    temp := head
    for temp.Next != nil {
        n++
        temp = temp.Next
    }
    //调整K
    k = k % n
    if k - n == 0 {
        return head
    }
    //形成环形链表
    temp.Next = head
    //定位到第 n - k 个节点，然后拆开。
    for i := 1; i < n-k; i++ {
        head = head.Next
    }
    newHead := head.Next
    // 拆开环
    head.Next = nil

    return newHead
}

发表回复

后才能评论

评论(9)

  • Mr.肖 永久会员 2024年3月27日 下午7:48

    时间复杂度：O(N),最坏情况下，遍历两次链表
    时间复杂度：O(1)

    class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return null;
        }
        if(head.next == null){
            return head;
        }

        int n = 0;
        ListNode cur = head;

        //统计链表数量
        while(cur != null){
            n++;
            cur = cur.next;

        }

        k = k%n;

        //成环
        cur = head.next;
        ListNode pre = head;
        while(cur.next != null){
            cur = cur.next;
            pre = pre.next;
        }
        cur.next = head;

        //断环
        cur = head;
        for(int i = 1; i < n - k; i++ ){
            cur = cur.next;
        }
        head = cur.next;
        cur.next = null;

        return head;
    }

}
  • 少年不识流川枫 永久会员 2024年2月28日 上午11:36 
    class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        //  求出链表的长度n
        int n = 1;
        ListNode a = head;
        while(a != null && a.next != null){
            a = a.next;
            n++;
        }

        int newk = k % n;   //此时只需要走最后一个循环（k<=n,一次循环内，K>n多次循环用最后一次所以取模）

        if(newk - n == 0){//此时特殊，刚好一个轮回，回到最初的原点，直接原链表哦！！！
            return head;
        }
        // 下面是变化的 newk一定小于长度n
        // 找到裁剪线的前驱，目标节点需要作为头节点,目标节点是n-k+1，前驱是n-k
        ListNode temp = head;
        // 前驱从1  ~ n-k    走n-k-1步
        for(int i = 0; i < n - newk -1; i++){
            temp = temp.next;  // temp走到前驱，即是3
        }
        ListNode b = head;
        for(int i = 0; i < n - newk; i++){
            b = b.next;  // b走到目标，即是4
        }
        // 此时head=1，temp=3，b=4，a=5，a.next=null
        //下来拆链，补链就可
        temp.next = null;
        a.next = head;
        return b;
    }
}

    这里我用的是拆链
    就是将前驱和目标那个线断掉，变成两个链表再组合下，返回目标节点，就是整合链表的头，

  • Yuki 永久会员 2024年2月1日 上午9:37

    重写

    class Solution {
    public:
    ListNode* rotateRight(ListNode* head, int k) {
    //先剪枝,旋不旋转一个样儿
    if(headnullptr||head->nextnullptr||k0){
    return head;
    }

        //剪枝后的链表中节点数一定＞1，先计算链表长度
    ListNode*cur=head;
    int len=1;
    while(cur->next!=nullptr){
        cur=cur->next;
        len++;
    }

    //走7步和走2步效果一样
    int step=(k>len)?(k%len):k;
    int add=len-step;//断链的位置

    //链表成环
    cur->next=head;
    while(add--){
        cur=cur->next;
    }

    //断链
    ListNode*ret=cur->next;
    cur->next=nullptr;

    return ret;
}

    };

  • uu 永久会员 2023年9月21日 下午3:19 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// 时间复杂度：O(2n)
// 空间复杂度：O(1)
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode tail = head;
        int count = 1, diff = 0;
        if(head == null || k == 0) return head;
        while(tail.next != null) {
            count++;
            tail = tail.next;
        }
        // 找到新头节点的位置
        if(k <= count){
            diff = Math.abs(count - k);
        } else {
            diff = count - k % count;
        }
        // 连成环
        tail.next = head;
        for(int i = 0; i < diff; i++) {
            tail = tail.next;
        }
        // 找到新头节点，然后破环
        head = tail.next;
        tail.next = null;
        return head;
    }
}
  • 阿尚 普通 2023年9月17日 下午2:23 
    class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }


        k = k % n;
        if (k == 0) {
            return head;
        }

        iter.next = head;
        //找到第n - k个节点
        for (int i = 0; i < n - k; i++) {
            iter = iter.next;
        }
        ListNode newHead = iter.next;

        //断开链表
        iter.next = null;
        return newHead;
    }
}
  • 泡芙 永久会员 2023年9月10日 下午11:25

    闭合为环

    • Time：O(n)，最坏的情况下，需要遍历链表两次
    • Space：O(1）
    class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        // 统计个数
        int n = 1;
        ListNode temp = head;
        while (temp.next != null) {
            n ++;
            temp = temp.next;
        }

        // 如果k>n,取余数
        k = k % n;
        if (k - n == 0) {
            return head;
        }

        // 成环
        temp.next = head;

        // 在n-k切断
        for (int i = 1; i < n - k; i ++) {
            head = head.next;
        }
        ListNode newHead = head.next;
        // 拆开环
        head.next = null;
        return newHead;
    }
}
  • 阿尚 普通 2023年8月18日 下午2:43 
    class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null) {
            return head;
        }
        int n = 1;
        ListNode iter = head;
        while (iter.next != null) {
            iter = iter.next;
            n++;
        }

        int add = n - k % n;
        if (add == n) {
            return head;
        }

        iter.next = head;//此时iter位于链表尾部节点，将next指向head构成一条圆环
        while (add-- > 0) {
            iter = iter.next;
        }
        ListNode newHead = iter.next;
        iter.next = null;
        return newHead;
    }
}
  • 帅气的冬瓜 普通 2023年6月29日 上午9:14

    打卡

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理