卖萌的弱渣

I am stupid, I am hungry.

Rotate List

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

Example

Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

Solution

  • Find the new head
  • Connect the old head into new head list
(Rotate-List.py) download
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

# 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):
        if head == None or head.next == None:
            return head
        l = 1
        i = 0
        tmp = head
        # Get the length 
        while tmp.next != None:
            l += 1
            tmp = tmp.next
        dummy_node = ListNode(-1)
        dummy_node.next = head
        k = k%l
        if k == 0:
            return head
        while i<l-k:
            dummy_node = dummy_node.next
            i += 1
        newhead = dummy_node.next
        dummy_node.next = None
        # connect the old head to new head 
        tmp = newhead
        while tmp.next != None:
            tmp = tmp.next
        tmp.next = head
        return newhead