前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Leetcode][python]Rotate List/旋转链表

[Leetcode][python]Rotate List/旋转链表

作者头像
蛮三刀酱
发布2019-03-26 16:19:11
4580
发布2019-03-26 16:19:11
举报
文章被收录于专栏:蛮三刀的后端开发专栏

题目大意

将一个链表中的元素向右旋转k个位置。

解题思路

参考:http://www.cnblogs.com/zuoyuan/p/3785465.html 解题思路:循环右移一条链表,比如k=2,(1,2,3,4,5)循环右移两位变为(4,5,1,2,3)。由于k值有可能比链表长度大很多,所以先要用一个count变量求出链表的长度。而k%count就是循环右移的步数。

代码

代码语言:javascript
复制
# Definition for singly-linked list.
# class ListNode(object):
#     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 k == 0:
            return head
        if head == None:
            return head
        dummy = ListNode(0)
        dummy.next = head
        p = dummy

        count = 0
        # 统计链表长度(这里实际上是从0开始数,数到4就结束,正好5个。)
        while p.next:  
            p = p.next
            count += 1
        step = count - ( k % count )

        # 此时p是最后一个数5,p.next指向null
        # p.next指向第一个数,这样p就是0,1,2,3,4,5,1,2,3,4,5
        p.next = dummy.next  
        for i in range(0, step):
            p = p.next

        # 此时p是最后一个未翻转的数3,将其下一个数4,放到head节点
        head = p.next
        # 此时head是4,5,1,2,3,4,5,1,2,3,4,5
        p.next = None
        # 此时head是4,5,1,2,3
        return head

总结

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年10月13日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目大意
  • 解题思路
  • 代码
  • 总结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档