[LeetCode] Challenge log 61

Posted on | Edited on |
61. Rotate List

Analysis:

  1. It is equivalent to finding the last k nodes and make them the head.
  2. If k > len(list), k = k % len(list)

Algorithm:

  1. let fast be k steps ahead of slow.
  2. forward both pointer until fast is the last node
  3. now slow is the pre of the last kth node

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

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if k == 0 or not head: return head
        newHead = ListNode(0)
        newHead.next = head

        # fast is k ahead of slow
        slow = newHead
        fast = newHead
        count = 0
        while count < k:
            if fast.next:
                fast = fast.next
                count += 1
            else:
                fast = newHead
                k = k % count
                count = 0
                if k == 0: return head

        
        # slow is the pre of the new head 
        while fast.next:
            fast = fast.next
            slow = slow.next
            
        # paste
        if slow == newHead: 
            return head
        else:
            fast.next = head
            res = slow.next
            slow.next = None
            return res
0%