deepSWE.io

Reverse Linked List

Linked ListTwo Pointers

EasyLeetCode #206

10 min

Problem Statement

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

Example

Example 1:

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

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

Constraints

The number of nodes in the list is the range [0, 5000].
-5000 ≤ Node.val ≤ 5000

Iterative Solution Walkthrough

The iterative solution uses three pointers: `prev`, `curr`, and `nextTemp`. We iterate through the list, and for each node, we reverse its `next` pointer to point to the `prev` node.

curr

Click 'Next' to start reversing the list.

Algorithm Steps

Initialize `prev` to `null` and `curr` to `head`.
While `curr` is not `null`, do the following:
Store the next node in `nextTemp`.
Set `curr.next` to `prev`.
Move `prev` to `curr`.
Move `curr` to `nextTemp`.
When the loop finishes, `prev` will be the new head of the reversed list.

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
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        return prev

Recursive Approach

The recursive solution is a bit more subtle. The idea is to reverse the rest of the list, and then attach the current node to the end of the reversed list.

Algorithm Steps

Base Case: If the head is `null` or `head.next` is `null`, return the head.
Recursively call the function with `head.next`. This will reverse the rest of the list and return the new head.
Set `head.next.next` to `head` to reverse the pointer of the next node.
Set `head.next` to `null` to break the original link.
Return the new head of the reversed list.

Recursive 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]:
        if not head or not head.next:
            return head
        
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return new_head