Jobs

Interviews

Discussions

Rotate List

Medium

Amazon

2 views

Topics:

Linked Lists

You are given the head of a singly linked list. Your task is to rotate the list to the right by k places, where k is a non-negative integer. The rotation should be performed in-place.

For example:

If the linked list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2, the rotated list should be 4 -> 5 -> 1 -> 2 -> 3.
If the linked list is 0 -> 1 -> 2 and k = 4, the rotated list should be 2 -> 0 -> 1.
If the linked list is empty, return null.

Constraints:

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

Write a function that takes the head of the linked list and an integer k as input and returns the head of the rotated linked list.

Rotate List

Medium

Amazon

2 views

Topics:

Linked Lists

You are given the head of a singly linked list. Your task is to rotate the list to the right by k places, where k is a non-negative integer. The rotation should be performed in-place.

For example:

If the linked list is 1 -> 2 -> 3 -> 4 -> 5 and k = 2, the rotated list should be 4 -> 5 -> 1 -> 2 -> 3.
If the linked list is 0 -> 1 -> 2 and k = 4, the rotated list should be 2 -> 0 -> 1.
If the linked list is empty, return null.

Constraints:

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

Write a function that takes the head of the linked list and an integer k as input and returns the head of the rotated linked list.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty (head is null)? What should I return in that case?
Is `k` guaranteed to be non-negative? What should happen if `k` is larger than the number of nodes in the linked list?
What is the data type of the values stored in the linked list nodes? Are there any constraints on their range?
Should the original linked list be modified, or should I create a new one?
Is there a maximum number of nodes that I should expect in the linked list?

Brute Force Solution

Approach

We need to shift a list of items by a certain amount. The brute force method involves repeatedly moving items from one end of the list to the other, one position at a time, until we've shifted enough.

Here's how the algorithm would work step-by-step:

Imagine you have a list of things and you want to move everything a certain number of places to the right.
Take the last item in the list and move it to the front.
Now all the other items have shifted one spot to the right.
Repeat this process of taking the last item and putting it at the front as many times as the shifting amount says.
After repeating this process the requested number of times, the list will have been shifted correctly.

Code Implementation

def rotate_list_brute_force(input_list, rotation_amount):
    list_length = len(input_list)

    # Normalize rotation amount to avoid unnecessary rotations
    effective_rotation = rotation_amount % list_length

    for _ in range(effective_rotation):
        # Store the last element before rotation

        last_element = input_list[-1]

        # Insert the last element at the beginning
        input_list.insert(0, last_element)

        # Remove the duplicated last element
        del input_list[-1]

    return input_list

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates k times, where k is the amount to rotate the list. In each iteration, the algorithm moves the last element to the front of the list, which takes O(n) time because shifting the remaining elements requires traversing the list. Therefore, the time complexity is O(n*k), where n is the length of the list and k is the number of rotations.

Space Complexity

O(1) – The provided algorithm modifies the input list in-place. It does not create any additional data structures like arrays or hash maps to store intermediate results or track visited locations. Therefore, the space used is independent of the input list size N. The space complexity is constant, or O(1).

Optimal Solution

Approach

The problem asks us to shift the elements in a chain of items. The clever trick is to realize you don't need to move items one by one. Instead, think of cutting and rearranging the chain.

Here's how the algorithm would work step-by-step:

First, figure out the actual number of shifts needed by handling cases where the shift amount is larger than the number of items.
Find the breaking point in the chain. This is the spot where you'll cut the chain into two pieces.
Break the chain into two parts at that point.
Swap the order of the two parts to rotate the chain.
Connect the two parts back together to form the rotated chain.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def rotate_right(head, rotation_amount):
    if not head:
        return None

    list_length = 1
    tail_node = head
    while tail_node.next_node:
        tail_node = tail_node.next_node
        list_length += 1

    # Effective rotation amount handles rotations > list length.
    effective_rotation = rotation_amount % list_length
    if effective_rotation == 0:
        return head

    # Find the node before the new head.
    new_tail_position = list_length - effective_rotation
    current_node = head

    for _ in range(new_tail_position - 1):
        current_node = current_node.next_node

    # Break the list into two parts.
    new_head = current_node.next_node
    current_node.next_node = None

    # Connect the tail to the original head.
    tail_node.next_node = head
    return new_head

Big(O) Analysis

Time Complexity

O(n) – The algorithm first determines the effective number of rotations by using the modulo operator, which takes constant time. It then traverses the linked list once to find the (n - k)th node (where n is the length of the list and k is the effective number of rotations). After finding this node, it modifies pointers a constant number of times to perform the rotation. Since traversing the list to find the breaking point dominates the execution time and involves visiting each node once, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm operates by identifying a 'breaking point', cutting, and rearranging the chain 'in-place'. It does not create new lists or data structures whose size depends on the input list's size, N. Only a few pointer or variable manipulations are needed to swap the two chain segments. Thus, the auxiliary space used is constant and independent of N.

Edge Cases

Case	How to Handle
head is null	Return null immediately to avoid NullPointerException.
Empty list (head is null) and k is 0	Return null as there's nothing to rotate.
Single node list	Return the head itself as rotating doesn't change anything.
k is 0	Return the original head without any changes.
k is a large value, potentially larger than the length of the list	Calculate k % length to get the effective rotation value.
k is equal to the length of the linked list	Return the original head as rotating by the length has no effect.
List with many nodes (performance concerns)	Ensure solution avoids unnecessary iterations by calculating effective k and correctly relinking nodes.
List with only two nodes, and k = 1	Handle the swapping of head and tail correctly.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked list be empty (head is null)? What should I return in that case?
Is `k` guaranteed to be non-negative? What should happen if `k` is larger than the number of nodes in the linked list?
What is the data type of the values stored in the linked list nodes? Are there any constraints on their range?
Should the original linked list be modified, or should I create a new one?
Is there a maximum number of nodes that I should expect in the linked list?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a list of things and you want to move everything a certain number of places to the right.
Take the last item in the list and move it to the front.
Now all the other items have shifted one spot to the right.
Repeat this process of taking the last item and putting it at the front as many times as the shifting amount says.
After repeating this process the requested number of times, the list will have been shifted correctly.

Code Implementation

def rotate_list_brute_force(input_list, rotation_amount):
    list_length = len(input_list)

    # Normalize rotation amount to avoid unnecessary rotations
    effective_rotation = rotation_amount % list_length

    for _ in range(effective_rotation):
        # Store the last element before rotation

        last_element = input_list[-1]

        # Insert the last element at the beginning
        input_list.insert(0, last_element)

        # Remove the duplicated last element
        del input_list[-1]

    return input_list

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The problem asks us to shift the elements in a chain of items. The clever trick is to realize you don't need to move items one by one. Instead, think of cutting and rearranging the chain.

Here's how the algorithm would work step-by-step:

First, figure out the actual number of shifts needed by handling cases where the shift amount is larger than the number of items.
Find the breaking point in the chain. This is the spot where you'll cut the chain into two pieces.
Break the chain into two parts at that point.
Swap the order of the two parts to rotate the chain.
Connect the two parts back together to form the rotated chain.

Code Implementation

class ListNode:
    def __init__(self, value=0, next_node=None):
        self.value = value
        self.next_node = next_node

def rotate_right(head, rotation_amount):
    if not head:
        return None

    list_length = 1
    tail_node = head
    while tail_node.next_node:
        tail_node = tail_node.next_node
        list_length += 1

    # Effective rotation amount handles rotations > list length.
    effective_rotation = rotation_amount % list_length
    if effective_rotation == 0:
        return head

    # Find the node before the new head.
    new_tail_position = list_length - effective_rotation
    current_node = head

    for _ in range(new_tail_position - 1):
        current_node = current_node.next_node

    # Break the list into two parts.
    new_head = current_node.next_node
    current_node.next_node = None

    # Connect the tail to the original head.
    tail_node.next_node = head
    return new_head

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
head is null	Return null immediately to avoid NullPointerException.
Empty list (head is null) and k is 0	Return null as there's nothing to rotate.
Single node list	Return the head itself as rotating doesn't change anything.
k is 0	Return the original head without any changes.
k is a large value, potentially larger than the length of the list	Calculate k % length to get the effective rotation value.
k is equal to the length of the linked list	Return the original head as rotating by the length has no effect.
List with many nodes (performance concerns)	Ensure solution avoids unnecessary iterations by calculating effective k and correctly relinking nodes.
List with only two nodes, and k = 1	Handle the swapping of head and tail correctly.