leetcode61：Rotate List-旋转列表-将列表向右循环移k位一.题目描述-Rotate List二.解题思路总结

60 阅读 0 评论 40 点赞

我是靠谱客的博主优雅康乃馨，最近开发中收集的这篇文章主要介绍leetcode61：Rotate List-旋转列表-将列表向右循环移k位一.题目描述-Rotate List二.解题思路总结，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Rotate List-源码

一.题目描述-Rotate List
二.解题思路
- 2.1 思路一(Naive)——每次循环右移一位+做k次循环
- 2.2 思路二——循环右移k次，找关键中断点，调整头尾指针
- 2.3 思路三——快慢指针法：
总结

一.题目描述-Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

原题链接： https://leetcode.com/problems/rotate-list/

二.解题思路

2.1 思路一(Naive)——每次循环右移一位+做k次循环

考虑到要求循环右移k位，那么只需要先编写一个每次移动一位的函数，然后调用k次即可。但是显然这种方法蠢萌蠢萌的，使用后实测发现Time Limit Exceeded。原因是k可能会很大，当len(list)也很长时，总是这样循环遍历效率极低。

2.2 思路二——循环右移k次，找关键中断点，调整头尾指针

观察发现，当进行循环右移时，找关键点应当是从右往左(也就是从尾到头)查找，以Example1 为例：

Input: 1->2->3->4->5->NULL, k = 2
从右往左查找，第2位是’4‘，所以此处’4‘就是新链表的头节点，’3‘是新链表的尾节点，只需要重新调整链表中指针指向即可。

考虑到可能出现k > len(list)的情况，此时只需简单处理，令k = k % len(list)即可解决。
回顾步骤1和2会发现当前的解决方法是从尾部往头部找关键点，对于单向链表而言，想要实现这一点比较麻烦。所以我们可以使用等价的向左移位来代替向右移位。具体而言向右循环移动** k 次，等价于向左循环移位 len(list)-k **次。向左移位时找关键点只需要就是从头向尾查找，非常方便。

具体代码-Python3代码：（C++或者java可以轻易套用此思路进行处理）

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
        # 由于K可能会大于len(list),需要先求模
        lenlist = self.getLen(head)
        head = self.rotateKstepToleft(head, lenlist-(k%lenlist))
        return head
    
    def getLen(self, head):
        len = 0
        while head is not None:
            head = head.next
            len += 1
        return len
    
    def getTail(self, head):
        if head is None:
            return None
        while head.next is not None:
            head = head.next
        return head
    
    def rotateKstepToleft(self, head, K):
        # 先预处理，使得K必定小于len(list)
        # 首先从1开始算起, 查找第K位
        if K == 0 or K == self.getLen(head):
            return head
        newtail = head
        while K > 1:
            newtail = newtail.next
            K -= 1
        newhead = newtail.next
        oritail = self.getTail(head)
        oritail.next = head
        newtail.next = None
        return newhead

上述代码关键在于rotateKstepToleft函数。以Example1为例，当该函数执行完while循环后，newtail为’3‘、newhead为’4‘、oritail为’5‘，head’为‘1的状态。进而根据头尾关系调整指针指向即可。

2.3 思路三——快慢指针法：

该方法其实只是作为思路2的一个变换版本，目的是复习一下快慢指针的使用。思路如下：
由思路2的分析可知，我们只需要找到关键节点(不妨定义为newtail以及newhead)，那么我们只需要设置fast，slow两个指针。让fast比slow先走k步，然后二者再同步，那么当fast到达尾部时，slow已经指向了newtail，同时可以进一步获取newhead。
代码如下：

	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
	        # 由于K可能会大于len(list),需要先求模
	        lenlist = self.getLen(head)
	        k = k % lenlist
	        fast = head
	        slow = head
	        while (k > 0): # 让fast先走k步
	            fast = fast.next
	            k -= 1
	        # 二者同步走,直到fast触底
	        while ((fast is not None) and (fast.next is not None)):
	            fast = fast.next
	            slow = slow.next
	        # 此时slow位置就是newtail，所以需要判断它是否与原来的tail重合
	        # fast.next 应该与 head接上
	        if (slow.next is None): 
	            return head
	        fast.next = head
	        newhead = slow.next
	        slow.next = None
	        return newhead
	    
	    def getLen(self, head):
	        len = 0
	        while head is not None:
	            head = head.next
	            len += 1
	        return len