61.Rotate_List(Medium).md

61. Rotate List (Medium)

Date and Time: Aug 6, 2024, 17:08 (EST)

Link: https://leetcode.com/problems/rotate-list/

Question:

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]

Edge case:

Input: head = [], k = 0

Output: []

Constraints:

• The number of nodes in the list is in the range [0, 500].

• -100 <= Node.val <= 100

• 0 <= k <= 2 * 10^9

Walk-through:

Rotate the list to the right by k places is the same as rotate the list by k % length, and we are only moving the last k to the front of the list, so the length - kth element is the newHead of the list.

Python Solution:

# 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: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head
        length = 1
        tail = head
        while tail.next:
            tail, length = tail.next, length + 1
        k = k % length
        if k == 0:
            return head
        curr = head
        for _ in range(length - k - 1):
            curr = curr.next
        newHead = curr.next
        curr.next = None  # Cut the linked list
        tail.next = head
        return newHead

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Java Solution:

C++ Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL) {
            return head;
        }
        int length = 1;
        ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
            length++;
        }
        k = k % length;
        if (k == 0) {
            return head;
        }
        ListNode* curr = head;
        for (int i = 0; i < length - k - 1; i++) {
            curr = curr->next;
        }
        ListNode* newHead = curr->next;
        curr->next = NULL;
        tail->next = head;
        return newHead;
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	36 ms	16.5 MB
Java	ms	MB
C++	0 ms	16.6 MB