https://leetcode.com/problems/rotate-list/
Rotate List
Total Accepted: 50875 Total Submissions: 233034 Difficulty: Medium
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.
Code
# 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
len_cnt = 0
tail_reach = False
fast = head
while k:
len_cnt += 1
if not fast.next:
tail_reach = True
fast = head
else:
fast = fast.next
k -= 1
if tail_reach:
k %= len_cnt
if fast == head:
return head
slow = head
while fast.next:
fast = fast.next
slow = slow.next
fast.next = head
new_head = slow.next
slow.next = None
return new_head
Idea
Use `fast` pointer to traverse `k` nodes. Then use a slow pointer to traverse from head. Both fast and slow pointers traverse one node by one node, until fast pointer reaches the end (line 35-37). Therefore, the slow pointer traverses exactly len(nums)-k nodes. Its next node should be the new head.
More succinct code can be found: https://discuss.leetcode.com/topic/14470/my-clean-c-code-quite-standard-find-tail-and-reconnect-the-list