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

清疚 2022-06-07 06:18 159阅读 0赞

## 题目大意 ##

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

## 解题思路 ##

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

## 代码 ##

# 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

## 总结 ##

[http_www.cnblogs.com_zuoyuan_p_3785465.html]: http://www.cnblogs.com/zuoyuan/p/3785465.html