What is the time complexity of Reverse Linked List?

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

What data structures are used to solve Reverse Linked List?

This problem uses Linked List, Recursion. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Reverse Linked List?

Insight 1: The core idea is to iterate through the linked list, changing the `next` pointer of each node to point to the previous node. This requires careful manipulation of pointers. Insight 2: Three pointers are crucial: `prev`, `curr`, and `next`. `prev` tracks the previously visited node, `curr` is the currently processed node, and `next` stores a temporary reference to the next node to avoid losing it.

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

Reverse Linked List - LeetCode 206 Solution

Q: Which companies ask LeetCode 206. Reverse Linked List in interviews?

This problem is frequently asked at Accenture, ByteDance, Cisco, Deloitte, Expedia and 25 more companies.

Reverse Linked List - Complete Solution Guide

Reverse Linked List is LeetCode problem 206, a Easy 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 singly linked list, reverse the list, and return the reversed list . Example 1: Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Example 2: Input: head = [1,2] Output: [2,1] Example 3: Input: head = [] Output: [] Constraints: The number of nodes in the list is the range [0, 5000] . -5000 <= Node.val <= 5000 Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Detailed Explanation

The problem asks you to reverse a singly linked list. A singly linked list is a data structure where each node points to the next node in the sequence. The input is the head (first node) of the linked list, and the output should be the head of the reversed linked list. For example, if the input list is 1->2->3->4->5, the output should be 5->4->3->2->1. The list can be empty or contain only one node.

Solution Approach

The provided code uses an iterative approach to reverse the linked list. It iterates through the list, reversing the links between nodes one by one. This is done by keeping track of the previous node (`prev`), the current node (`curr`), and the next node (`next`). In each iteration, the `next` pointer of the current node is redirected to point to the previous node. Then, `prev` and `curr` are updated to move to the next node in the original list.

Step-by-Step Algorithm

Step 1: Initialize three pointers: `prev` to `NULL` (or `nullptr`), `curr` to the `head` of the list, and `next` to `NULL` (or `nullptr`).
Step 2: Iterate while `curr` is not `NULL` (or `nullptr`).
Step 3: Store the `next` node in the `next` pointer: `next = curr->next`.
Step 4: Reverse the link: `curr->next = prev`.
Step 5: Update `prev` and `curr`: `prev = curr`, `curr = next`.
Step 6: After the loop, `prev` will point to the new head of the reversed list. Return `prev`.

Key Insights

Insight 1: The core idea is to iterate through the linked list, changing the `next` pointer of each node to point to the previous node. This requires careful manipulation of pointers.
Insight 2: Three pointers are crucial: `prev`, `curr`, and `next`. `prev` tracks the previously visited node, `curr` is the currently processed node, and `next` stores a temporary reference to the next node to avoid losing it.
Insight 3: Handling the base cases (empty list or single-node list) is important. The algorithm should gracefully handle these scenarios without errors.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Recursion.

Companies

Asked at: Accenture, ByteDance, Cisco, Deloitte, Expedia, Google, J.P. Morgan, Luxoft, NetApp, Nvidia, Oracle, Ozon, PayPal, Paytm, Qualcomm, SAP, Samsung, ServiceNow, Siemens, Snap, Tesla, Tinkoff, Visa, X, Yandex, Yelp, Zenefits, Zopsmart, Zynga, tcs.

Reverse Linked List | LeetCode 206

Easy

Linked List Recursion

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 reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 206: Reverse Linked List - Detailed explanation and solution approaches.

Topics

Linked List Recursion

Companies

AccentureByteDanceCiscoDeloitteExpediaGoogleJ.P. MorganLuxoft

Stats

Difficulty:Easy

Languages:4

Companies:30

Problem #:206

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

6 steps

1
Step 1: Initialize three pointers: `prev` to `NULL` (or `nullptr`), `curr` to the `head` of the list, and `next` to `NULL` (or `nullptr`).
2
Step 2: Iterate while `curr` is not `NULL` (or `nullptr`).
3
Step 3: Store the `next` node in the `next` pointer: `next = curr->next`.
4
Step 4: Reverse the link: `curr->next = prev`.
5
Step 5: Update `prev` and `curr`: `prev = curr`, `curr = next`.
6
Step 6: After the loop, `prev` will point to the new head of the reversed list. Return `prev`.

💡

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 algorithm iterates through the linked list once, performing constant-time operations in each iteration. Therefore, the time complexity is linear, O(n), where n is the number of nodes. The algorithm uses a constant amount of extra space to store the three pointers; hence, the space complexity is O(1).

📖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

Recursive Approach

A recursive solution reverses the list by recursively calling the function on the rest of the list and then appending the current node to the end of the reversed sublist.

Time: O(n)Space: O(n) - due to recursive call stack

Trade-offs: The recursive approach is often considered less efficient due to the overhead of recursive calls and potential stack overflow issues for very large lists. The iterative approach is generally preferred for its efficiency and avoidance of stack overflow errors.

✨

Key Insights

1Insight 1: The core idea is to iterate through the linked list, changing the `next` pointer of each node to point to the previous node. This requires careful manipulation of pointers.
2Insight 2: Three pointers are crucial: `prev`, `curr`, and `next`. `prev` tracks the previously visited node, `curr` is the currently processed node, and `next` stores a temporary reference to the next node to avoid losing it.
3Insight 3: Handling the base cases (empty list or single-node list) is important. The algorithm should gracefully handle these scenarios without errors.

📚

Key Terms Explained

For Students

Recursion

A function that calls itself to solve smaller versions of the same problem.

Linked List

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

Edge Cases

Edge case 1: Empty list: The `while` loop condition (`curr != NULL`) handles this correctly; the function returns `prev`, which is initially `NULL`, indicating an empty reversed list.
Edge case 2: Single-node list: The loop runs once, reversing the `next` pointer to `NULL`. The function correctly returns the single node as the head of the reversed list.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrect pointer manipulation: Forgetting to store the `next` node before modifying `curr->next` can lead to losing parts of the list.

✗Common mistake 2: Off-by-one errors: Incorrectly handling the loop termination or pointer updates can lead to incorrect results or infinite loops.

✅

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: Undoing operations: Imagine a system where operations are stored in a linked list. Reversing the list could be used to undo operations in reverse chronological order.

🏦Real-world scenario 2: Data processing: Reversing a linked list could be a preprocessing step in algorithms that require processing data in reverse order.

💡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

Don't rush. Explain your thought process clearly. Easy problems are often about communication.

⚠️ 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: June 27, 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 13

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

@InterviewProJul 6

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Reverse Linked List"?

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

🤖 Need help with this problem?