7.15 Reverse Linked List

7.15.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 206
• Difficulty: Easy
• URL: https://leetcode.com/problems/reverse-linked-lc-list/
• Tags: Grind 75, Blind 75, NeetCode 150
• Techniques: Two Pointers, Recursion, Linked List

7.15.2 Description

Reverse a singly linked lc-list.

7.15.3 Solution - Iterative Two Pointers

7.15.3.1 Walkthrough

Maintain prev, curr, and next. Iteratively reverse the next pointer of each node until the lc-list is reversed.

7.15.3.2 Analysis

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

7.15.3.3 Code - Java

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;
}

7.15.4 Solution - Recursive

7.15.4.1 Walkthrough

Recursively reverse the rest of the list, then set head.next.next = head and head.next = null to reverse the current edge.

7.15.4.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(n) recursion stack

7.15.4.3 Code - Java

public ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}