MicrosoftData StructuresMedium

Reverse a Linked List

Linked ListAlgorithmsRecursion

Question

Given the head of a singly linked list, reverse the list and return the reversed list.

Answer

Iterative Approach:

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

Recursive Approach:

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

Explanation

**Time Complexity:** O(n) - traverse the list once **Space Complexity:** - Iterative: O(1) - Recursive: O(n) due to call stack The iterative approach is preferred for its constant space complexity.