Reverse Linked List

Reversing a linked list is a common problem in data structures. You can reverse a linked list by changing the “next” pointers of each node.

Here’s a step-by-step approach to reverse a singly linked list:

Initialize Three Pointers: prev, current, and next_temp. Set prev to None, and current to the head of the linked list.
Iterate Through the List: While current is not None, perform the following steps: a. Set next_temp to the next node of current. b. Change the next of current to prev, effectively reversing the current node. c. Move prev and current one step forward.
Set New Head: Once current is None, the head of the reversed linked list is where prev is pointing.

Here’s the code implementing this logic:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head

        while current is not None:
            next_temp = current.next # temporarily store the next node
            current.next = prev      # reverse the current node
            prev = current           # move prev to this node
            current = next_temp      # move to the next node

        head = prev # after the loop, prev is at the new head
        return head

Explanation:

prev keeps track of the previously reversed node.
current is the node that we’re currently reversing.
next_temp temporarily stores the next node so that we don’t lose the reference to the rest of the list.
The loop continues until current reaches the end of the list.
After the loop, prev will be pointing to the new head of the reversed list.

The time complexity of this code is O(n), where n is the number of nodes in the linked list, and the space complexity is O(1), as we’re only using a constant amount of extra space.

Reversing a sublist of a linked list between given positions left and right can be done by manipulating pointers. Here’s a simple step-by-step guide to doing this:

Initialize Variables: You’ll need a few variables to track the current node, previous node, and the node before the left position.
Move to the Left Position: Iterate through the list until you reach the left position, keeping track of the node before left.
Reverse the Sublist: Iterate from the left to the right position, reversing the pointers to reverse the sublist.
Reconnect the Sublist: Connect the node before the left position to the new start of the sublist, and connect the new end of the sublist to the node after the right position.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        # Move to the left position
        for _ in range(left - 1):
            prev = prev.next

        current = prev.next

        # Reverse the sublist
        for _ in range(right - left):
            tmp = current.next
            current.next = tmp.next
            tmp.next = prev.next
            prev.next = tmp

        return dummy.next

This code first creates a dummy node to simplify handling the edge case when left is 1. Then, it iterates to the left position and performs the reversal by repeatedly moving the next node to the start of the sublist.

The time complexity of this algorithm is ( O(n) ), where ( n ) is the length of the linked list, and the space complexity is ( O(1) ), as it uses a constant amount of extra space.

Reverse using Recursion

Recursion provides a straightforward way to reverse a linked list by breaking the problem into smaller, more manageable parts. The key insight here is that reversing a smaller linked list and attaching the head to its end effectively reverses the entire list.

Basic Thought Process

Base Case: When you reach the end of the linked list, recursion ends. This last node becomes the new head.
Recursive Case: For each node, you first recurse on the subsequent nodes.
Reversal: On the way back from recursion, reverse the pointers between adjacent nodes.

Step-by-step Explanation

Traversal to the End: Starting from the head, traverse the linked list until the end is reached. This is also your base case; when you reach a null reference, you’ve hit the end.
Head Becomes Tail: The end node becomes the new head of the reversed list.
Unwind Stack: As the recursion stack unwinds, you’re essentially walking back from the tail to the head of the original list.
Switch Pointers: For each node, set its next node’s next pointer to point back to the node itself. This is where the reversal happens.
Null Termination: Set the next pointer of what was originally the head node to null, to properly terminate the reversed list.

How Recursion Works Here:

The reversal logic (switching pointers) is simple and isolated, making it easier to reason about.
Recursion naturally follows the linked list structure, breaking the problem down into smaller, identical problems.

Example:

Original: 1 -> 2 -> 3 -> null
After Traversal: 1 <- 2 <- 3
New Head: 3 -> 2 -> 1 -> null

In summary, recursion simplifies the reversal process by isolating the reversal logic, maintaining state through the call stack, and naturally following the list structure.

Simplify the problem. How would you solve reverse the entire linked list. Recursive Approach for Reverse Linked List Input: Head of the linked list Output: Head of the linked list
Sentinal node (dummy node) Save the current head as sentinel node’s next

We probably don’t need a sentinel sentinel.next = head

1->2->3->4->5->NULL ^ ^

5->4->3->2->1->NULL ^

1->2->3->4->5->NULL ^ ^ 1<-2 3->4->5->null (reversing the link before the recursive calls)

1->2->3->4->5->NULL ^ ^

Head becomes the new tail (Create a link to new head) Tail becomes the new head (Create a new tail) Reverse Links

Base Case
 If the node is null, return
 
Goal: Reverse every link in the linked list

Recursive Cases
    Unit of Work
        - Reverse the links with leader and follower (follower is one step ahead of leader)      
   - When should we do the UoW (before or after the recursive call)

How many pointers do we need? We can have three pointers Separate 2,3,4 from existing linked list Point the head to the tail of the … (This is two-pass )
1->2->3->4->5->6
1->2->3->4->5->NULL ^ ^
1->4->3->2->5
Where should we initialize the pointer? We initialize the follower to m and the leader to n
Can we reverse the links like we did for Reverse Linked List problem? It is easier to swap the values pointed to by the leader and follower
We can traverse forward by doing follower.next but how do you go back?
Base Case
- When do we stop the recursion? stop instance variable (boolean) follower instance variable
- When we hit the null node or

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def wrapper(right, m, n)
   if n == 1 
     return
   end

    right = right.next

    if m > 1
        @left = @left.next
    end

    wrapper(right, m-1, n-1)

    if @left == right || right.next == @left
        @stop = true
    end

    if !@stop
        @left.val, right.val = right.val, @left.val
        @left = @left.next
    end
end

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @param {Integer} m
# @param {Integer} n
# @return {ListNode}
def reverse_between(head, m, n)
  @stop = false
  @left = head
  right = head

    wrapper(right, m, n)

    return head
end

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end

def wrapper(right, m, n)
    if n == 1
        return
    end

    right = right.next

    if m > 1
        @left = @left.next
    end

    wrapper(right, m-1, n-1)

    if @left == right || right.next == @left
        @stop = true
    end

    if !@stop
        @left.val, right.val = right.val, @left.val

        @left = @left.next
    end
end

# @param {ListNode} head
# @param {Integer} m
# @param {Integer} n
# @return {ListNode}
def reverse_between(head, m, n)
@stop = false
@left = head
wrapper(head, m, n)
    return head
end

Identifying Problem Isomorphism

In “Reverse Linked List” you are given a singly linked list and the task is to reverse the list.

A simpler problem to “Reverse Linked List” is “Delete Node in a Linked List”. In this problem, you are only required to delete a specific node from a linked list, which requires a basic understanding of how linked lists work and how to traverse them.

An approximately isomorphic problem to “Reverse Linked List” is “Palindrome Linked List”. In this problem, you need to determine whether a given singly linked list is a palindrome. To solve this, one common approach is to reverse the second half of the linked list and compare it with the first half. The reversing part is similar to the “Reverse Linked List” problem.

A more complex problem is “Reverse Nodes in k-Group”. In this problem, you are asked to reverse nodes in a linked list in groups of k. This involves not only reversing linked list nodes but also handling the grouping and maintaining the connections between different groups.

In ascending order of complexity, these problems are arranged as:

“Delete Node in a Linked List” - Delete a specific node in a linked list.
“Reverse Linked List” - Reverse the nodes of a linked list.
“Palindrome Linked List” - Check if a linked list is a palindrome, involves reversing part of the list.
“Reverse Nodes in k-Group” - Reverse nodes in groups of k in a linked list, involves complex manipulations on linked list nodes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution(object):
    def reverseList(self, head):
        prev = None
        curr = head

        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        return prev       

Problem Classification

Data Structures: This problem involves working with a fundamental data structure - a singly linked list.
Linked List Manipulation: The core task of this problem is to manipulate the pointers in a linked list to reverse the list.
In-place Algorithm: The problem requires an in-place solution, which means we’re modifying the input data structure (linked list) itself and not creating a new one.
Linear Data Structures: Linked list is a linear data structure where elements are arranged sequentially, and each element links to its next element.
Pointers: This problem requires the use of pointers (or references) to iterate through the linked list and to change the links between nodes.

Language Agnostic Coding Drills

Understanding Linked Lists: The first fundamental concept here is understanding linked lists and how they work. A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. Each element (node) contains a reference (link) to the next node in the sequence. In this problem, the given linked list is a singly linked list, where each node only has one link to the next node.
Understanding Variables: The code uses three variables: prev, curr, and next. “prev” represents the previous node, “curr” represents the current node, and “next” represents the next node.
Understanding Looping Through a Linked List: The next concept to understand is how to traverse or loop through a linked list. In this code, a while loop is used to iterate through each node in the linked list until the end of the list (when curr is None).
Reversing Pointers in a Linked List: The core task here is to reverse the direction of the pointers of the linked list nodes. This is done inside the while loop where each node’s next pointer is set to the previous node.
Understanding “None” in Python (or Null in other languages): “None” represents the absence of a value or a null point. It’s used here to initialize the previous node (prev) and to signify the end of the linked list.
Working with Multiple Assignments: The code uses multiple assignments in a single line to simultaneously update the prev, curr and next pointers.

The problem solving approach for this problem is:

Start with the head of the list, initialize the current node (curr) to the head and the previous node (prev) to None.
Inside a loop, make a copy of the next node before changing any references.
Change the next of the current node to point to the previous node.
Move one step ahead in the original list by setting prev to curr and curr to next.
Repeat steps 2-4 until the end of the list is reached.
The reversed list’s head is the last node in the original list, which is now pointed to by prev.
Return prev as the head of the reversed list.

Targeted Drills in Python

Understanding Linked Lists: The first step is to understand how linked lists work. You can create a basic LinkedList class and Node class for this purpose. A LinkedList consists of nodes, and each node has a value and a reference to the next node. You can practice creating a LinkedList and adding nodes to it.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        if not self.head:
            self.head = Node(value)
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = Node(value)

Understanding Looping Through a Linked List: Write a function to print all the elements of a linked list. This will help you understand how to traverse a linked list.

1
2
3
4
5
def printLinkedList(head):
    current = head
    while current:
        print(current.value)
        current = current.next

Reversing Pointers in a Linked List: The next step is to understand how to reverse a linked list. You can create a function that takes the head of a linked list and returns the head of the reversed linked list.

1
2
3
4
5
6
7
8
9
def reverseLinkedList(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

The final solution is simply the “reverseLinkedList” function. This function starts with a pointer at the head of the list and another pointer at None (which represents the previous node initially). It iterates through the list, setting the next node of the current node to the previous node, effectively reversing the list. After visiting all nodes, the function returns the pointer to the new head of the reversed list.

title: Reverse Linked List excerpt: This covers reversing a linked list using recursion. tags: return-phase-of-recursion

The links are reversed during the return phase of recursion.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
def reverse(head)
  # no need to reverse if head is nil
  # or there is only 1 node.
  if (head.nil? || head.next.nil?)
    return head
  end

  reversed_head = reverse(head.next)

  head.next.next = head
  head.next = nil
  
  return reversed_head
end

list_head = create_linked_list([7, 14, 21, 28])
print "Original: "
display(list_head)
list_head = reverse(list_head)
print "After Reverse: "
display(list_head)