Welcome to this tutorial on solving a classic problem that often appears in software engineering interviews: reversing a singly linked list. This challenge, commonly found on LeetCode (LeetCode 206), is a fantastic way to understand essential concepts in data structures and algorithms.

Whether you're new to engineering interviews or an experienced engineer brushing up on your skills, this guide aims to equip you with the knowledge to confidently tackle linked list problems.

Introduction to the Problem

The problem statement is straightforward: given the head of a singly linked list, reverse the list, and return the head of the reversed list. For instance:

• Input: head = [1,2,3,4,5], Output: [5,4,3,2,1]

  

  Input: head = [1,2], Output: [2,1]

  

  Input: head = [], Output: []

Understanding the Solution

To reverse a linked list, we can use the two-pointer technique, a common strategy for linked list problems. This involves using two pointers, typically named prev and current, to traverse the list and reverse the links between nodes.

Big O Notation Analysis

• Time Complexity: O(n), where n is the number of nodes in the linked list. We need to traverse all nodes once.

• Space Complexity: O(1) for the iterative approach, as we only use a fixed amount of extra space. For the recursive approach, it's O(n) due to the call stack.

Recursive Solution in Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(self, head: ListNode) -> ListNode:
    # Base case: if list is empty or has only one element
    if not head or not head.next:
        return head
    # Reverse the rest of the list
    new_head = self.reverseList(head.next)
    # Set the next of the next node to the current node to reverse
    head.next.next = head
    head.next = None  # Set the next of the current node to None
    return new_head  # Return the new head of the reversed list

Iterative Solution in Python

def reverseList(self, head: ListNode) -> ListNode:
    prev, cur = None, head
    while cur:
        temp = cur.next  # Store the next node
        cur.next = prev  # Reverse the current node's pointer
        prev = cur  # Move prev to current
        cur = temp  # Move to the next node
    return prev  # Prev will be the new head

Recursion vs. Iteration: A Comparison

Solution in TypeScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val===undefined ? 0 : val);
        this.next = (next===undefined ? null : next);
    }
}

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let cur: ListNode | null = head;
    while (cur !== null) {
        let temp: ListNode | null = cur.next;  // Store next node
        cur.next = prev;  // Reverse the link
        prev = cur;  // Move prev forward
        cur = temp;  // Move cur forward
    }
    return prev;  // New head of the reversed list
}

Solution in Java

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 ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode temp = cur.next;  // Store next node
        cur.next = prev;  // Reverse the link
        prev = cur;  // Move prev forward
        cur = temp;  // Move cur forward
    }
    return prev;  // New head of the reversed list
}

Conclusion

Reversing a linked list is a fundamental problem that tests your understanding of linked lists and pointer manipulation. By mastering both iterative and recursive approaches, you'll be well-prepared for software engineering interviews.

Remember, practice is key to becoming proficient in these concepts. I hope this guide helps you on your journey to becoming a more confident and skilled software engineer.

Thank you for taking the time to read this post. Your dedication to learning and improving is what makes the journey of programming so rewarding. Happy coding!