LeetCode 61 [Rotate List]

原题

给定一个链表,旋转链表,使得每个节点向右移动k个位置,其中k是一个非负数。

样例
给出链表1->2->3->4->5->null和k=2
返回4->5->1->2->3->null

解题思路

  • 分解问题,各个击破
  • 首先找到链表的尾部,并且计算长度
  • 找到需要旋转的起点位置
  • 最后做出相应的连接,旋转链表
  • 注意移动的位置实际是(k % len)

完整代码

# 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 not head or k == 0:
            return head
        
        # find the tail
        tail = head
        len = 1
        while tail.next != None:
            tail = tail.next
            len += 1
        if k % len == 0:
            return head
            
        # find the rotate place
        slow = fast = head
        for i in range(k % len):
            fast = fast.next
        while fast.next != None:
            fast = fast.next
            slow = slow.next
            
        tail.next = head
        head = slow.next
        slow.next = None
        return head
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容