Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
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:
Input: 0->1->2->NULL, k = 4 Output:2->0->1->NULLExplanation: 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->NULLrotate 4 steps to the right:2->0->1->NULL
Solution: Find the prev of the new head
Step 1: Get the tail node T while counting the length of the list.
Step 2: k %= l, k can be greater than l, rotate k % l times has the same effect.
Step 3: Find the previous node P of the new head N by moving (l – k – 1) steps from head
Step 4: set P.next to null, T.next to head and return N
Time complexity: O(n) n is the length of the list
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (!head) return head; int l = 1; ListNode* tail = head; while (tail->next) { tail = tail->next; ++l; } k %= l; if (k == 0) return head; ListNode* prev = head; while (--l > k) prev = prev->next; ListNode* new_head = prev->next; tail->next = head; prev->next = nullptr; return new_head; } }; |
Java
|
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 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null) return null; int l = 1; ListNode tail = head; while (tail.next != null) { tail = tail.next; ++l; } k %= l; if (k == 0) return head; ListNode prev = head; for (int i = 0; i < l - k - 1; ++i) { prev = prev.next; } ListNode new_head = prev.next; prev.next = null; tail.next = head; return new_head; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Solution: def rotateRight(self, head: ListNode, k: int) -> ListNode: if not head: return head tail = head l = 1 while tail.next: tail = tail.next l += 1 k = k % l if k == 0: return head prev = head for _ in range(l - k - 1): prev = prev.next new_head = prev.next tail.next = head prev.next = None return new_head |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment