【Leetcode】61.旋转链表

xushaojieaaa 发布于2019-07-30 17:44 / 3491人阅读

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

作者: 码蹄疾
毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者；
负责小米应用商店、日历、开屏广告业务线研发；
主导小米广告引擎多个模块重构；
关注推荐、搜索、广告领域相关知识;

给定一个链表，旋转链表，将链表每个节点向右移动 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

题解

昨晚吃火锅吃撑了回来这道题，还算顺利~~
链表的题目,其实就是在考指针交换,这个题目先让链表连成一个环，然后再切开就可以完成了。

python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        # 链表的节点个数
        count = 1
        cur = head
        while cur.next:
            count += 1
            cur = cur.next
        # 如果恰好走了一个环,就直接返回
        k = k % count
        if k == 0:
            return head
        cur.next = head
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        # 需要走count-k个,然后把链表切断
        for _ in range(count - k):
            prev = prev.next
        # 重新组成新的链表
        cur = prev.next
        new_head = cur
        
        prev.next = None

        return new_head

java版本

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

        int count = 1;
        ListNode cur = head;
        while (cur.next != null) {
            count++;
            cur = cur.next;
        }
        k = k % count;
        if (k == 0) {
            return head;
        }
        cur.next = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < count - k; i++) {
            prev = prev.next;
        }
        cur = prev.next;
        prev.next = null;
        return cur;
    }
}

热门阅读

【Leetcode】60. 第k个排列

技术文章汇总

GPU云服务器云服务器 C语言数据结构旋转链表 LeetCode 61vps 61cdn

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

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

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

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

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

imtianx 2019-07-25 14:27 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0