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
, andnext_temp
. Setprev
toNone
, andcurrent
to thehead
of the linked list. - Iterate Through the List: While
current
is notNone
, perform the following steps: a. Setnext_temp
to the next node ofcurrent
. b. Change the next ofcurrent
toprev
, effectively reversing the current node. c. Moveprev
andcurrent
one step forward. - Set New Head: Once
current
isNone
, thehead
of the reversed linked list is whereprev
is pointing.
Here’s the code implementing this logic:
|
|
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 beforeleft
. - Reverse the Sublist: Iterate from the
left
to theright
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 theright
position.
Here’s the code:
|
|
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
|
|
|
|
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.
|
|
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.
|
|
- 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.
|
|
- 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.
|
|
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.
|
|