Problem 46 - Reverse Linked List

Explore our archive for previous posts.

Problem 45 - Middle of the Linked List

Problem 44 - Minimum Depth of Binary Tree

Problem 43 - Maximum Depth of Binary Tree

Question

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

Approach

This problem involves reversing a singly linked list. Here's a high-level approach:

1. Iterative Approach: Use three pointers - prev, current, and next.

2. Iterate Through the List: Move through the list, reversing the link from current to prev.

3. Update Pointers: Move prev, current, and next pointers one step forward.

4. Return New Head: After reaching the end of the list, prev will be the new head.

Solution

Solve it here

/**
 * 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; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        // Initialize pointers
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;

        // Iterate through the list
        while (current != null) {
            // Save the next node
            next = current.next;
            
            // Reverse the link
            current.next = prev;
            
            // Move pointers one step forward
            prev = current;
            current = next;
        }

        // Prev is the new head of the reversed list
        return prev;
    }
}

Time and space complexity

Time Complexity: The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. We traverse the list once.

Space Complexity: The space complexity is O(1) as we only use a constant amount of extra space for the three pointers. The algorithm is performed in-place and does not require additional data structures.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!

Nailing Coding Interviews: Mindset Matters

Ethical Dilemmas in Coding Interviews: Should You Reveal Prior Knowledge?