!!Given the head of a linked list, rotate the list to the right by k places.!!
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head == None:
return []
count = 1
temp = head
while (temp.next != None):
count +=1
temp = temp.next
# count = length, so the length remaining same seq is count - k -1
if k == 0:return head;
#else
head = temp.next
temp.next = None
while(count -k -1): #ensure the amount of reversed nodes
#to reverse
head = temp.next
temp.next = None #clearance
return head
A better way:
#先把链表首尾相连，再找到位置断开循环
class Solution(object):
def rotateRight(self, head, k):
if head is None or head.next is None: return head
start, end, len = head, None, 0
while head:
end = head
head = head.next
len += 1
end.next = start
pos = len - k % len
while pos > 1:
start = start.next
pos -= 1
ret = start.next
start.next = None
return ret