Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details

describe

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: the head = [1, 2, 3, 4, 5], k = 2 Output:,5,1,2,3 [4]Copy the code

Note:

  • The number of nodes in the list is in the range [0, 500].
  • -100 <= Node.val <= 100
  • 0 <= k <= 2 * 10^9

parsing

Given the head pointer to the list, return the list after you rotate the list k bits to the right.

The meaning of the question is very simple, in fact, the idea is also according to the operation description of the question:

  • Let’s go through the list and find the length of the list
  • Then attach the head to the end of the list
  • Num =N-k%N; num=N-k%N; next = None
  • Finally, return the transformed head result

The time complexity is O(N), and the space complexity is O(1).

answer

class Solution(object):
    def rotateRight(self, head, k):
        if not head or k==0:
            return head
        N = 1
        result = head
        while result.next:
            N += 1
            result = result.next
        result.next = head
        num = N - k%N 
        result = head
        end = None
        for _ in range(num):
            end = result
            result = result.next
        end.next = None
        return result
Copy the code

The results

Given in the Python online submission for the Rotate List. Memory Usage: Submissions in the Python online List for Rotate List.Copy the code

parsing

In fact, there is a more awkward method, that is, put all the values of the nodes into a list, and then calculate that the first num nodes need to be placed at the end of the list. This solution is relatively straightforward, but the space complexity will increase to O(N), because the new space is created to store the values of all nodes. The time hasn’t changed. It’s order N.

answer

class Solution(object):
    def rotateRight(self, head, k):
        if not head or k==0:
            return head
        L  = []
        while head:
            L.append(head.val)
            head = head.next
        result = dummy = ListNode(-1)
        N = len(L)
        num = N-k%N 
        L = L[num:] + L[:num]
        for v in L:
            dummy.next = ListNode(v)
            dummy = dummy.next
        return result.next
        
Copy the code

The results

Each node in the Python online submission List is linked to the node. Memory Usage: 13 MB, less than 60.71% of Python online submissions for the Rotate List.Copy the code

The original link

Leetcode.com/problems/ro…

Your support is my biggest motivation