XYZ CODE: reverse linked list

Reverse a linked list.

The problem has many solutions with various time and space complexity. Before we start, there are a few questions we need to ask:

can the linked list be empty?
can the head be null?
is there a head node or not?
should we preserve the original linked list?
is the linked list doubly linked or singly linked?
is there circle in the linked list?

The data structure of singly linked list is a value + a pointer to the next node.

Linked List

public class Node {
int value;
MyNode next;
}

MyNode.java

Problem 1,

reversed a linked list with head node: for example head -> 1 -> 2 -> 3 -> 4 -> 5 should be reversed to head -> 5 -> 4 -> 3 -> 2 -> 1.
Here are 5 example solutions:

Solution 1. reverse the linked list with the aid of a stack.

We can first iterate through the original linked list, push the elements into a stack, then iterate through the stack, pop the elements and create a new linked list.

The code to iterate through the linked list is:

Node current = head;
while(current.next != null) {
current = current.next;
//do something with current
}

We have to traversal the nodes twice. The time complexity is O(N)

We need a stack to store the elements temporally, we also need extra space to store the new linked list besides the original linked list, the space complexity is O(N).

SolutionOne.java

SolutionOneTest.java

Solution 2. reverse the linked list by copying the node value but changing the next node.

We can iterate through the original linked list, for the first node, we copy the value to a new node, set the new node's next to null to mark the tail. We then iterate through the rest of the nodes in the original linked list, have a variable remember the previous node created. For the current node, we copy the value to a new node, set the next field to the previous node created. We finally create a new head pointing to the last node created for reversed linked list.

We have to traversal the nodes once, the time complexity is O(N).

We need one variable to store the current node temporally, we also need extra space to create the new linked list besides the original linked list, the space complexity is O(N) as well.

SolutionTwo.java

SolutionTwoTest.java

Solution 3. reverse the linked list by recursively reverse the sub linked list.

In order to reverse head -> 1 -> 2 -> 3 -> 4 -> 5, we first reverse 2 -> 3 -> 4 -> 5, which is 5 -> 4 -> 3 -> 2. We then attach the first node to the tail, thus get 5 -> 4 -> 3 -> 2 -> 1.

With the same manner, in order to reverse 2 -> 3 -> 4 -> 5, we first reverse 3 -> 4 -> 5, which is 5 -> 4 -> 3. We then attach the node 2 to the tail, thus get 5 -> 4 -> 3 -> 2.

We can reverse 3 -> 4 -> 5 by reversing 4 -> 5 first.

We can reverse 4 -> 5 by reversing 5 first.

Reversing 5 doesn't need anything.

head.next points to the tail of the sub linked list

Node recursiveReverse(Node head) {
if(head == null || head.next == null) {
return head;
} else {
Node newHead = recursiveReverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}

We have to visit each node at least once, the time complexity is O(N).

The recursive call implicitly used a stack to store the temporal values -- the recursive function's call stack -- and the space complexity is O(N).

SolutionThree.java
SolutionThreeTest.java

Solution 4. reverse the original linked list by changing its next field in place.

While iterating through the original linked list, we always remember the previous node visited and the next node we will visit. Then we change the current node's next to point to the previous node visited. Since we have the next node we visit stored, we can continue traversal the original linked list.

while(current != null) {
next = current.next;
current.next = pre;
pre = current;
current = next;
}

We have to iterate the linked list once, the time complexity is O(N).

We need 3 variables to store the previous node, current node and next node, we reverse the original linked list in place without creating a new one, the space complexity is O(1).

SolutionFour.java
SolutionFourTest.java

Solution 5. reverse the original linked list by inserting the nodes behind the head.

We iterate through the original linked list, for the current node, we remove it from the linked list, then insert the removed node behind the head node.

remove a node then add behind head

while(current.next != null) {
next = current.next;
current.next = current.next.next;
next.next = head.next;
head.next = next;
}

We have to iterate the linked list once, the time complexity is O(N).

We need a variable to store the current node visited, we also need another variable to store the next node we will visit in order to continue the traversal after we removing the current node, the space complexity is O(1).

SolutionFive.java
SolutionFiveTest.java

We haven't done yet, we took time to exam this simple problem, it will pay back. We can use these solutions to solve a bunch of other problems.

Problem 2:

Reverse linked list that have no head node: for example 1 -> 2 -> 3 -> 4 -> 5 should be reversed to 5 -> 4 -> 3 -> 2 -> 1.

Same as problem 1, there are also 5 solutions for problem 2. This problem is even simpler, since we don't have to specially treat the head node.

Solution 1. reverse the linked list with the aid of a stack.

We can first iterate through the original linked list, push the elements into a stack, then iterate through the stack, pop the elements and create a new linked list.

We have to traversal the nodes twice. The time complexity is O(N)

We need a stack to store the elements temporally, we also need extra space to store the new linked list besides the original linked list, the space complexity is O(N).

ExtendSolutionOne.java

ExtendSolutionOneTest.java

Solution 2. reverse the linked list by copying the node value but changing the next node.

We have to traversal the nodes once, the time complexity is O(N).

Solution 3. reverse the linked list by recursively reverse the sub linked list.

In order to reverse 1 -> 2 -> 3 -> 4 -> 5, we first reverse 2 -> 3 -> 4 -> 5, which is 5 -> 4 -> 3 -> 2. We then attach the first node to the tail, thus get 5 -> 4 -> 3 -> 2 -> 1.

With the same manner, in order to reverse 2 -> 3 -> 4 -> 5, we first reverse 3 -> 4 -> 5, which is 5 -> 4 -> 3. We then attach the node 2 to the tail, thus get 5 -> 4 -> 3 -> 2.

We can reverse 3 -> 4 -> 5 by reversing 4 -> 5 first.

We can reverse 4 -> 5 by reversing 5 first.

Reversing 5 doesn't need anything.

We have to visit each node at least once, the time complexity is O(N).

The recursive call implicitly used a stack to store the temporal values -- the recursive function's call stack -- and the space complexity is O(N).

ExtendSolutionThree.java
ExtendSolutionThreeTest.java

Solution 4. reverse the original linked list by changing its next field in place.

We have to iterate the linked list once, the time complexity is O(N).

We need 3 variables to store the previous node, current node and next node, we reverse the original linked list in place without creating a new one, the space complexity is O(1).

ExtendSolutionFour.java
ExtendSolutionFourTest.java

Solution 5. reverse the original linked list by inserting the nodes behind the head.

We iterate through the original linked list, for the current node, we remove it from the linked list, then insert the removed node behind the head node.

We have to iterate the linked list once, the time complexity is O(N).

We need a variable to store the current node visited, we also need another variable to store the next node we will visit in order to continue the traversal after we removing the current node, the space complexity is O(1).

ExtendSolutionFive.java
ExtendSolutionFiveTest.java

We still haven't done yet, there are similar problems that can be resolved the similar way.

Reverse a double linked list with head node.
Reverse a double linked list without head node.
Reversely print a single linked list with head node.
Reversely print a single linked list without head node.
Reversely print a double linked list with head node.
Reversely print a double linked list without head node.
Read in a sequence of numbers, print them in reverse order.
Read in a sequence of numbers, print them in order, then reverse order.
Read in a sequence of words, print them in reverse order.
Read in a sequence of words, print them in order, then reverse order.

The following is a similar but a little bit harder problem:

Problem:
Reverse a linked list with K nodes as a group.
For example, given linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7. If K = 2, the reversed linked list is 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 7. If K = 3, the reversed linked list is 3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7. If K = 4, the reversed linked list is 4 -> 3 -> 2 -> 1 -> 5 -> 6 -> 7.

Solution:
Step 1. Find the boundary of a K node group, store the previous node, head of the group, tail of the group, next node.
Step 2. Reverse the K node group.
Step 3. point the previous node to the head of the reversed K node group, point tail of the reversed K node group to the next node.
Step 4. advance the previous node, head of the group, tail of the group, next node for next K node group.

When K = 2, the above problem can also be described as:
Problem:
reverse the adjacent nodes on a linked list, for example, given 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7, the reversed linked list is 2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 7.

KReverseLinkedList.java

Some linked list re-order problems can explicitly involve linked list reverse.

Problem:
Given a linked list 0 -> 1 -> 2 -> 3 -> ... -> n-2 -> n-1 -> n, reorder the linked list as 0 -> n -> 1 -> n-1 -> 2 -> n-2 -> ...

Solution:
Q: Does this linked list single linked or double linked?
A: Single linked
Q: does the linked list has header node?
A: yes
Q: does 0 sized and 1 sized linked list allowed?
A: yes
Q: when there are 2 nodes in the linked list, we don't reorder, right?
A: right

find the linked list's middle point, divide the linked list into two sub linked list, reverse the second sub linked list, merge the two parts.
We can use fast/slow pointer to find the middle point. The fast pointer advances 2 nodes per iteration, while the slow pointer advances 1 node per iteration. They both start at head node, when fast pointer reaches the tail, slow pointer is at the middle point. We have to traversal the linked list once, then traversal half of the linked list to reverse it, then traversal 2 halves of the linked list to merge them, the time complexity is O(N). We only need a few pointers during traversal and merge, the space complexity is O(1).

ReorderLinkedList.java

Follow up question:
If the given linked list is double linked, can we find a better algorithm?

Solution:
If the linked list is double linked, we don't have to reverse the second half.

We can use fast/slow pointer to find the middle point. The fast pointer advances 2 nodes per iteration, while the slow pointer advances 1 node per iteration. They both start at head node, when fast pointer reaches the tail, slow pointer is at the middle point.

At this point, we don't have to reverse the second half, we can walk the slow pointer backward, then we walk down from head and insert the node the slow pointer pointing.

Problem: Reverse a linked list with circles.

Solution:

Reverse a linked list with circles is a harder problem. First of all we can not terminate the loop by checking current.next == null, instead, we need to first detect if there are circles in the linked list. In fact, a linked list has at most one circle, because each node can have only one next link. There is no way for a node on an existing circle to divert to another path in order to enter another circle. When there is a circle, there are 2 scenarios.

all the nodes are on the circle.
some of the nodes are not on the circle. In this scenario, the linked list can not be reversed. The starting point of the circle has 2 links pointing to it, but when reverse links, it can set only one next link.

Linked list with circle

Let's start with a simplifying assumption: all the nodes in the linked list are on the circle. In that case, we can specify the "head" of the circle, remember the head node, then use current.next == head to terminate the loop.

special case of circular linked list

1 -> 2 -> 3 -> 4 -> 5 -> 1

CircularSolutionFour.java
CircularSolutionFourTest.java

Once we know the solution of the previous problem, reversing a linked list with circles in its general form is easier.

First, we need to find the first node of a loop in the linked list. If there is no loop, we reverse the linked list with normal way. If there is a loop, then we divide the linked list into 2 pieces: the nodes in the linked list that leads to the circle and the nodes on the circle itself. If there are any nodes from head to the first node of a loop, then the linked list is not reversible, otherwise we reverse a linked circle.

How to find the first node of a loop is a separate problem by itself. Here is an outline of the approach.

Again, we can use fast/slow pointer to detect a circle. Once the two pointers meet, a circle is detected. We then follow the following 3 steps to find the first node in the linked list:

1. If a loop is found, initialize slow pointer to head, let fast pointer be at its position.
2. Move both slow and fast pointers one node at a time.
3. The point at which they meet is the start of the loop.

In case all nodes are on a circle, the start of the loop is calculated as the head.

Why this algorithm works need some math, we just take it as a matter of fact.