61.md

Rotate List

Description

link

---

Solution

• compute size of link list
• k = k % size
• use p, q to record rotate position
• rotate (tail.next = head; p.next = None; q become head)

---

Code

T : O(n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        p = head
        size = 0
        
        while p:
            size += 1
            p = p.next
            
        if not size:
            return None
        
        k %= size
        
        if not k:
            return head
        
        tail = head
        for _ in range(size-1):
            tail = tail.next
        
        p, q = head, head.next
        for _ in range(size-k-1):
            p = p.next
            q = q.next
        tail.next = head
        p.next = None
        return q