LeetCode 206: Reverse Linked List Solution

Problem Explanation

Explanation

To reverse a linked list, we can iterate through the list while reversing the pointers to point in the opposite direction. We need to keep track of the current node, the next node, and the previous node to perform the reversal.

Iterative Approach:
- Initialize three pointers: prev as null, curr as the head of the list, and next as null.
- Traverse the list while updating the pointers: set next to curr.next, point curr.next to prev, move prev to curr, and move curr to next.
- Return prev as the new head of the reversed list.
Recursive Approach:
- The base case is when the current node is null or the next node is null, return the current node.
- Recursively call the function on the next node, then reverse the pointers by setting curr.next.next to curr and set curr.next to null.
- Return the new head of the reversed list.

Time Complexity: O(n) where n is the number of nodes in the linked list.
Space Complexity: O(1) for the iterative approach and O(n) for the recursive approach due to the stack space used in recursion.

Solution Code

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = null;
        
        while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

Frequently Asked Questions

How to solve LeetCode 206 (Reverse Linked List)?

This page provides optimized solutions for LeetCode problem 206 (Reverse Linked List) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 206 (Reverse Linked List)?

The time complexity for LeetCode 206 (Reverse Linked List) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 206 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 206 in Java, C++, or Python.