[Leetcode] Rotate List 旋转链表

Yu_Huang 发布于2019-08-14 12:40 / 3496人阅读

摘要：不过，由于可能大于链表的长度，所以我们要先对取链表长度的模。代码计算链表长度如果不旋转或者原链表为空则直接返回让快指针先走步找到新头节点的前一个节点将后半部分放到前面来

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

双指针法 复杂度

时间 O(N) 空间 O(1)

思路

旋转链表的本质，就是把链表的后半部分放到前面来，所以关键在于如何找链表后半部分的起始节点。实际上，我们用一个快指针先走k步，然后快慢指针同时走，这样当快指针到末尾时，慢指针就到链表后半部分的起始节点了。不过，由于k可能大于链表的长度，所以我们要先对k取链表长度的模。要计算链表长度只要遍历一遍链表就行了。

注意

k取余后为0，或者原链表为空的情况下，都要直接返回原链表，不然将慢指针的下一个作为新链表头会出错。

代码

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode fast = head;
        int length = 0;
        // 计算链表长度
        while(fast != null){
            length++;
            fast = fast.next;
        }
        // 如果不旋转或者原链表为空 则直接返回
        if(head == null || k % length == 0){
            return head;
        }
        fast = head;
        // 让快指针先走k步
        for(int i = 0; i < k % length; i++){
            fast = fast.next;
        } 
        // 找到新头节点的前一个节点
        ListNode slow = head;
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        // 将后半部分放到前面来
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        return newHead;
    }
}

云服务器 GPU云服务器旋转-rotate C语言数据结构旋转链表 Rotate LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64627.html

LeetCode 61：旋转链表 Rotate List

摘要：给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。按上述思路解，与旋转数组那道题大同小异，来介绍另一种很简单高效的方法。只需在第个节点之后切断，首尾连接即可。另外可能大于链表长度，应当做求余运算。给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 Given a linked list, rotate the list to the ...

Hwg 2019-07-31 11:30 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
[LintCode/LeetCode] Rotate List

摘要：而后吾当依除取余之法，化大为小，则指针不致于越界也。后欲寻右起第结点，令快指针先行数日，及至两指针相距为，便吟鞭东指，与慢指针策马共进。快慢指针亦止于其所焉。舞动长剑，中宫直入，直取首级，而一掌劈空，已鸿飞冥冥。自此，一代天骄，霸业已成。 Problem Given a list, rotate the list to the right by k places, where k is...

Blackjun 2019-08-14 15:22 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0