Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/61.html
Given the head
of a linked list, rotate the list to the right by k
places.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output: [2,0,1]
Constraints:
- The number of nodes in the list is in the range
[0, 500]
. -100 <= Node.val <= 100
0 <= k <= 2 * 109
Algorithm
First traverse the original linked list to get the length n of the linked list, and then take the remainder of k
to n
, so that k must be less than n
.
Use the fast and slow pointers to solve, the fast pointer first walks k
steps, and then the two pointers go together, when the fast pointer reaches the end , The next position of the slow pointer is the head node of the new order, so that the linked list can be rotated.
Code
-
public class Rotate_List { /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode rotateRight(ListNode head, int k) { if (head == null) { return head; } // k could be larger than list-length int length = 0; ListNode p = head; while (p != null) { length++; p = p.next; } // avoid circle rotate k = k % length; if (k == 0) { return head; } // two pointers, j is k behind i ListNode i = head; while (k > 0) { i = i.next; k--; } ListNode j = head; while (i.next != null) { // i will stop at last node, j will stop at after-rotate end node i = i.next; j = j.next; } ListNode newHead = j.next; // @note: here, hidden assumption is "j.next != null” . eg: input: list=[1], k=0 j.next = null; // cut i.next = head; // link return newHead; } } public class Solution_make_circle { public ListNode rotateRight(ListNode head, int n) { if (head == null || head.next == null || n == 0) return head; // compare list length with k, what if k is extremely large ListNode ptail = head; int count = 1; while (ptail.next != null) { count++; ptail = ptail.next; } int cutoff = count - (n % count); ptail.next = head; // @note: connect head tail, making it circular list for (int i = 0; i < cutoff; i++) { ptail = ptail.next; } ListNode newhead = ptail.next; ptail.next = null; return newhead; } } } ############ /** * 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 (k == 0 || head == null || head.next == null) { return head; } int n = 0; for (ListNode cur = head; cur != null; cur = cur.next) { ++n; } k %= n; if (k == 0) { return head; } ListNode slow = head, fast = head; while (k-- > 0) { fast = fast.next; } while (fast.next != null) { slow = slow.next; fast = fast.next; } ListNode start = slow.next; slow.next = null; fast.next = head; return start; } }
-
// OJ: https://leetcode.com/problems/rotate-list/ // Time: O(N) // Space: O(1) class Solution { int getLength(ListNode *head) { int ans = 0; for (; head; head = head->next) ++ans; return ans; } public: ListNode* rotateRight(ListNode* head, int k) { if (!head) return nullptr; int len = getLength(head); k %= len; if (k == 0) return head; auto p = head, q = head; while (k--) q = q->next; while (q->next) p = p->next, q = q->next; auto ans = p->next; p->next = nullptr; q->next = head; return ans; } };
-
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def rotateRight(self, head: ListNode, k: int) -> ListNode: if k == 0 or head is None or head.next is None: return head n, cur = 0, head while cur: n, cur = n + 1, cur.next k %= n if k == 0: return head slow = fast = head for _ in range(k): fast = fast.next while fast.next: slow, fast = slow.next, fast.next start = slow.next slow.next = None fast.next = head return start ############ # 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): """ :type head: ListNode :type k: int :rtype: ListNode """ if not head: return head l = 1 p = head while p.next: l += 1 p = p.next k = k % l if k == 0: return head k = l - k % l - 1 pp = head print k while k > 0: pp = pp.next k -= 1 newHead = pp.next pp.next = None p.next = head return newHead
-
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */ public class Solution { public ListNode RotateRight(ListNode head, int k) { if (k == 0 || head == null || head.next == null) { return head; } var n = 0; for (ListNode cur = head; cur != null; cur = cur.next) { ++n; } k %= n; if (k == 0) { return head; } ListNode slow = head, fast = head; while (k-- > 0) { fast = fast.next; } while (fast.next != null) { slow = slow.next; fast = fast.next; } ListNode start = slow.next; slow.next = null; fast.next = head; return start; } }
-
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func rotateRight(head *ListNode, k int) *ListNode { if head == nil || head.Next == nil { return head } cur := head n := 0 for cur != nil { cur = cur.Next n++ } k %= n if k == 0 { return head } fast, slow := head, head for i := 0; i < k; i++ { fast = fast.Next } for fast.Next != nil { fast = fast.Next slow = slow.Next } ans := slow.Next slow.Next = nil fast.Next = head return ans }