LeetCode 61. Rotate List

''' Given a linked list, rotate the list to the right by k places, where k is non-negative. ''' # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def rotateRight1(self, head, k): """ :type head: ListNode :type k: int :rtype: ListNode """ #problem: when k is too large, the direct method cannot work, thus need to obtain the length of the list first if not head or not head.next: return head else: p1 = p2 = head dump = None for i in range(k): p2 = p2.next if not p2.next: dump = p2 p2.next = p1 if dump: dump = p2.next p2.next = None return dump else: while p2.next: p1 = p1.next p2 = p2.next p2.next = head dump = p1.next p1.next = None return dump #24ms, 10.9MB def rotateRight(self, head, k): if not head or not head.next: return head else: n = 1 p1 = head while p1.next: p1 = p1.next n += 1 p1.next = head k = k%n p2 = ListNode(0) p2.next = head for i in range(n-k): p2 = p2.next p3 = p2.next p2.next = None return p3