[Leetcode/Linked List] 206. Reverse Linked List

🔗 What Is a Linked List?

A linked list is a linear data structure where each element (node) points to the next one in the sequence.

Unlike arrays, which store elements in contiguous memory, a linked list connects scattered nodes using pointers.

 

🧱 Structure of a Node

Each node in a singly linked list has:

• val: the data (value)
• next: a reference (or pointer) to the next node

Example:

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

 

So a node like:

node = ListNode(3)

 

means: a node with value 3 and next set to None.

 

📏 How It Looks

Let’s say we want to store: 1 -> 2 -> 3

Visually:

[1 | o ] --> [2 | o ] --> [3 | / ]

 

Each box is a ListNode. The | o means a pointer to the next node. / means the end (None).

In code:

node3 = ListNode(3)
node2 = ListNode(2, node3)
node1 = ListNode(1, node2)

 

node1 is now the head of the list.

 

🔁 How to Traverse It

To go through a linked list:

current = head
while current:
	print(current.val)
    current = current.next

 

📚 Types of Linked Lists

Type	Description
Singly Linked	Each node points to the next node only
Doubly Linked	Each node points to both next and prev
Circular Linked	The last node points back to the head

✅ Why Use Linked Lists?

Pros:

• Efficient insert/delete operations (O(1)) if you know the node
• No need to shift elements like in arrays

Cons:

• Slower to access by index (O(n))
• Uses more memory (pointers)

---

✅ Iterative Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head

        while current:
            next_node = current.next  # temporarily store the next node
            current.next = prev       # reverse the current node's pointer
            prev = current            # move prev and current one step forward
            current = next_node

        return prev  # prev becomes the new head of the reversed list

✅ Recursive Solution:

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head