leetcode61 Rotate List

nodejh 发布于2019-08-16 10:36 / 2344人阅读

摘要：根据列表的长度，计算，也就是最短等价移动次数。之后利用双指针，保证头指针和尾指针之间的距离始终为，从而找到右边第个节点。这时候还计算数组的长度的话，反而降低了性能。

题目要求

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.

其实这题的描述有些不妥当，确切的说是将最右侧的节点依次移到最左侧作为头结点，一直移动到右侧第k个节点后结束。
还是以1->2->3->4->5->NULL为例
k=1 结果为：5->1->2->3->4->NULL
k=2 结果为：4->5->1->2->3->NULL
k=3 结果为：3->4->5->1->2->NULL
k=4 结果为：2->3->4->5->1->NULL
k=5 结果为：1->2->3->4->5->NULL
k=6 结果为：5->1->2->3->4->NULL

换句话说当k的值超过了list的长度len的时候，移动k次等价于移动k%len次

思路一：计算出list长度

即通过一次遍历，找到列表的末节点同时，计算出列表的长度。根据列表的长度，计算k%len，也就是最短等价移动次数。之后利用双指针，保证头指针和尾指针之间的距离始终为k，从而找到右边第k个节点。

    public ListNode rotateRight2(ListNode head, int k) {
        if(k==0 || head==null)
            return head;
        
        //get list length and last node
        ListNode last = head;
        int len = 1;
        while(last.next != null){
            last = last.next;
            len++;
        }
        
        
        k = k%len;
        if(k==0)
            return head;
        ListNode start = new ListNode(0);
        start.next = head;
        int count = len-k;
        while(count > 0){
            start = start.next;
            count--;
        }
        
        last.next = head;
        head = start.next;
        start.next = null;
        
        return head;
           
    }

思路二：简单优化

其实在某些情况下，k的值并不一定比数组的长度大。这时候还计算数组的长度的话，反而降低了性能。这个时候，可以将遍历的过程和头指针的移动结合起来。如果头指针移动到结尾而k并不是等于0，则可以得知k大于列表长度，同时这个过程还可以得出列表的长度。如果k等于0时，头指针未移动到末尾，则可以继续头指针和尾指针的同时移动，知道头指针到达数组的最后一个元素。
代码如下：

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return null;
        }
        ListNode firstPointer = head;
        int length = 0;
        while(firstPointer!= null && k > 0){
            k--;
            firstPointer = firstPointer.next;
            length++;
        }
        if(k == 0){
            if(firstPointer == null){
                return head;
            }
            ListNode secondPointer = head;
            while(firstPointer != null && firstPointer.next!=null){
                secondPointer = secondPointer.next;
                firstPointer = firstPointer.next;
            }
            firstPointer.next = head;
            ListNode result = secondPointer.next;
            secondPointer.next = null;
            return result;
        }else{
            return rotateRight(head, k%length);
        } 
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器服务器托管 Rotate 旋转-rotate Leetcod LeetCode

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

转载请注明本文地址：https://www.ucloud.cn/yun/70111.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] Rotate List 旋转链表

摘要：不过，由于可能大于链表的长度，所以我们要先对取链表长度的模。代码计算链表长度如果不旋转或者原链表为空则直接返回让快指针先走步找到新头节点的前一个节点将后半部分放到前面来 Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. For example: Gi...

Yu_Huang 2019-08-14 12:40 评论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】61.旋转链表

摘要：小米广告第三代广告引擎的设计者开发者负责小米应用商店日历开屏广告业务线研发主导小米广告引擎多个模块重构关注推荐搜索广告领域相关知识给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广告领域相关知识; ...

Jeffrrey 2019-08-19 11:06 评论0 收藏0
【Leetcode】61.旋转链表

摘要：小米广告第三代广告引擎的设计者开发者负责小米应用商店日历开屏广告业务线研发主导小米广告引擎多个模块重构关注推荐搜索广告领域相关知识给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。作者: 码蹄疾毕业于哈尔滨工业大学。小米广告第三代广告引擎的设计者、开发者；负责小米应用商店、日历、开屏广告业务线研发；主导小米广告引擎多个模块重构；关注推荐、搜索、广告领域相关知识; ...

imtianx 2019-07-25 14:27 评论0 收藏0