What is the time complexity of Rotate List?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Rotate List?

This problem uses Linked List, Two Pointers. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Rotate List?

Insight 1: We need to find the length of the linked list to handle cases where 'k' is larger than the length of the list. This is achieved by traversing the list once. Insight 2: The actual rotation happens by finding the new tail and new head after the rotation. We calculate where the new tail should be located and break the list into two segments to form the rotated list.

Which companies ask LeetCode 61. Rotate List in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, LinkedIn and 6 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Rotate List - LeetCode 61 Solution

Q: How to solve Rotate List?

The solution first calculates the length of the linked list. Then, it calculates the effective number of rotations by taking `k` modulo the length. After the effective rotation amount is determined, we connect the tail of the original list to the head to form a circular linked list. Then, we traverse the list to find the new tail, which will be `length - k - 1` nodes from the original head. Finally, we break the connection between the new tail and the node after it, making the node after the new tail as the new head.

Rotate List - Complete Solution Guide

Rotate List is LeetCode problem 61, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 * 10 9

Detailed Explanation

The problem requires us to rotate a singly linked list to the right by `k` places, where `k` is a non-negative integer. Rotating a list to the right means moving the last `k` elements to the beginning of the list and shifting the remaining elements to the right. If `k` is larger than the length of the list, we effectively rotate by `k % length`.

Solution Approach

The solution first calculates the length of the linked list. Then, it calculates the effective number of rotations by taking `k` modulo the length. After the effective rotation amount is determined, we connect the tail of the original list to the head to form a circular linked list. Then, we traverse the list to find the new tail, which will be `length - k - 1` nodes from the original head. Finally, we break the connection between the new tail and the node after it, making the node after the new tail as the new head.

Step-by-Step Algorithm

Step 1: Check if the linked list is empty or has only one node, or if k is zero. If so, return the original list.
Step 2: Calculate the length of the linked list by traversing it once. Also, save the last node as `tail`.
Step 3: Calculate the effective number of rotations by taking `k` modulo the length: `k = k % length`. If `k` becomes 0 after the modulo, it means no rotation is required, so return the original list.
Step 4: Connect the tail of the linked list to the head to form a circular linked list: `tail.next = head`.
Step 5: Calculate the number of steps needed to reach the new tail: `steps_to_new_tail = length - k - 1`.
Step 6: Traverse `steps_to_new_tail` nodes from the original head to find the new tail.
Step 7: The node after the new tail will be the new head: `new_head = new_tail.next`.
Step 8: Break the connection between the new tail and the new head: `new_tail.next = null`.
Step 9: Return the new head.

Key Insights

Insight 1: We need to find the length of the linked list to handle cases where 'k' is larger than the length of the list. This is achieved by traversing the list once.
Insight 2: The actual rotation happens by finding the new tail and new head after the rotation. We calculate where the new tail should be located and break the list into two segments to form the rotated list.
Insight 3: Handle edge cases such as an empty list, a list with only one node, or k equals to zero as they will result in the original list as the output.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Two Pointers.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, LinkedIn, Meta, Microsoft, Morgan Stanley, Oracle, Siemens, Yahoo.

Rotate List | LeetCode 61

Medium

Linked List Two Pointers

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

Solution Code

Available in:

/**
 * 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 || head.next == null || k == 0) {
            return head;
        }

        int length = 1;
        ListNode current = head;
        while (current.next != null) {
            current = current.next;
            length += 1;
        }

        ListNode tail = current;

        k = k % length;
        if (k == 0) {
            return head;
        }

        tail.next = head;

        int steps_to_new_tail = length - k - 1;
        ListNode new_tail = head;
        for (int i = 0; i < steps_to_new_tail; i++) {
            new_tail = new_tail.next;
        }

        ListNode new_head = new_tail.next;
        new_tail.next = null;

        return new_head;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 61: Rotate List - Detailed explanation and solution approaches.

Topics

Linked List Two Pointers

Companies

AdobeAmazonAppleBloombergLinkedInMetaMicrosoftMorgan Stanley

Stats

Difficulty:Medium

Languages:4

Companies:11

Problem #:61

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

9 steps

1
Step 1: Check if the linked list is empty or has only one node, or if k is zero. If so, return the original list.
2
Step 2: Calculate the length of the linked list by traversing it once. Also, save the last node as `tail`.
3
Step 3: Calculate the effective number of rotations by taking `k` modulo the length: `k = k % length`. If `k` becomes 0 after the modulo, it means no rotation is required, so return the original list.
4
Step 4: Connect the tail of the linked list to the head to form a circular linked list: `tail.next = head`.
5
Step 5: Calculate the number of steps needed to reach the new tail: `steps_to_new_tail = length - k - 1`.
6
Step 6: Traverse `steps_to_new_tail` nodes from the original head to find the new tail.
7
Step 7: The node after the new tail will be the new head: `new_head = new_tail.next`.
8
Step 8: Break the connection between the new tail and the new head: `new_tail.next = null`.
9
Step 9: Return the new head.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is determined by the traversals of the linked list, which are proportional to its length. The space complexity is constant because we only use a fixed number of variables to store the head, tail, and other temporary pointers.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using an Array (Not Recommended)

Store the linked list nodes in an array. Rotate the array using array rotation techniques, and then reconstruct the linked list from the rotated array.

Time: O(n)Space: O(n)

Trade-offs: This approach uses O(n) extra space to store the nodes in the array. It might be easier to conceptualize but is less efficient than the O(1) space solution. Not ideal for very large linked lists due to the space overhead.

✨

Key Insights

1Insight 1: We need to find the length of the linked list to handle cases where 'k' is larger than the length of the list. This is achieved by traversing the list once.
2Insight 2: The actual rotation happens by finding the new tail and new head after the rotation. We calculate where the new tail should be located and break the list into two segments to form the rotated list.
3Insight 3: Handle edge cases such as an empty list, a list with only one node, or k equals to zero as they will result in the original list as the output.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Empty list (head is null). The code handles this case by returning null directly in the beginning.
Edge case 2: List with only one node (head.next is null). The code handles this case similarly to the empty list case, by returning the original head.
Edge case 3: k is zero. In this case the original linked list is returned
Edge case 4: k is a multiple of the length of the list (k % length == 0). In this case no effective rotation is performed, and the original list should be returned.
Edge case 5: Large value of k. The code uses the modulo operator (%) to reduce k to its effective value (k % length), preventing unnecessary rotations.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where k is greater than the length of the linked list. Failing to take the modulo of k with the length of the list can lead to incorrect results or infinite loops.

✗Common mistake 2: Not handling edge cases such as an empty list or a list with only one node. This can lead to null pointer exceptions.

✗Common mistake 3: Forgetting to break the connection between the new tail and the new head after rotation. This will result in a circular linked list, which is not what the problem asks for.

✗Common mistake 4: Incorrectly calculating the number of steps to the new tail, off-by-one errors frequently happen there.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Playlist rotation. Imagine a music playlist represented as a linked list. Rotating the playlist by 'k' songs allows users to start listening from a different point in the playlist.

🏦Real-world scenario 2: Data stream processing. In circular buffers or data streams, rotating the data can be useful to process the data in a different order or to prioritize certain elements.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: August 1, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Rotate List"?

For this medium-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?