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