algoadvance

Leetcode 206. Reverse Linked List

Problem Statement

Reverse a singly linked list.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Clarifying Questions

1. What should be returned?
   Return the head of the reversed linked list.

2. Can the list be empty?
   Yes, the input list can be empty. In this case, return null.

3. Is the input list guaranteed to be a singly linked list?
   Yes.

Strategy

1. Iterative Approach:
   • Initialize three pointers: prev as null, curr as head, and next as null.
   • Traverse through the linked list.
   • In each iteration:
     • Store the next node.
     • Reverse the link of the current node.
     • Move the prev and curr one step forward.
2. Recursive Approach:
   • Base case: If the current node is null or the next node is null, return the current node.
   • Recursively reverse the rest of the list.
   • Adjust the pointers to reverse the current node.

Code

Here is the Java implementation using both iterative and recursive approaches.

Iterative Approach

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

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

Recursive Approach

public class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }
}

Time Complexity

• Iterative Approach: O(n), where n is the number of nodes in the linked list. We traverse the list only once.
• Recursive Approach: O(n), where n is the number of nodes in the linked list. There is a function call for each node.

In both approaches, the space complexity is O(1) for the iterative approach and O(n) for the recursive approach (due to the stack used for function calls).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?