Rotate List

题目描述

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

For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

解题方法

two pointer方法，找到第length-k的个，然后将它的next设为None, 并且将原来list的end的next设为head, 再return原来的第length-k + 1个

注意点

• k有可能大于length

Solution

# 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:
            return None
        length = self.getLength(head)
        k = k % length
        q = length - k
        p = 0
        pointer1 = head
        while p < q - 1:
            pointer1 = pointer1.next
            p += 1
        pointer2 = head
        while pointer2.next:
            pointer2 = pointer2.next
        pointer2.next = head
        result = pointer1.next
        pointer1.next = None
        return result

    def getLength(self, head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

Reference