In this post I will reverse a linked list in Java. As I mentioned in a previous post, I am in the process of refreshing recursion using Java. In the next few days I will pick up a few more problems and post my approach.
In this post I will deal with 206. Reverse Linked List. If interested please take a look at the requirements for the problem and then give it a try before looking at solutions.
As a follow up to this problem, a linked list can be reversed using an iterative or a recursive approach. Not sure if there is a way to post and check both approaches. I did submit both solutions on different times.
As you know I believe software development at all stages and levels is both science and art. You need to learn and practice. I personally prefer developing software using my computers and tools. When experimenting and learning I like to do it from scratch. If you want to test code on your computer, you will 
have to develop test scaffolding. That helps to better understand the requirements are and in most cases there might be something new to learn.
In this case I will develop the test scaffolding and different approaches to the requirements using a Windows 10 computer and the Java programming language with the VSCode IDE. Of course you can use a different computer and IDE, but unless you wish to port the code to other programming language, you should be all set.
The problem has a single example.
1->2->3->4->5->NULL main <<< head: 1->2->3->4->5->NULL main <<< head: 5->4->3->2->1->NULL main <<< head: 1->2->3->4->5->NULL main <<< head: 5->4->3->2->1->NULL
I decided to use the same input format as the one shown by LeetCode. Chances are that the format was just an array holding integer values. The problem has a single output line which shows the reversed linked list. In my test scaffolding, the first line shows the contents of the linked list prior to being reversed.
The second line shows the output of reversing the linked list. The third line reverses the previous results and the fourth line does it again. This will be illustrated by the test scaffolding.
/**
* Definition for singly-linked list.
*/
class ListNode {
// **** members ****
int val;
ListNode next;
// **** constructors ****
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
// **** added for testing (not required) ****
@Override
public String toString() {
return "" + this.val;
}
}
The ListNode class shows the members and methods available to construct the linked list. As you can see I added the toString method. I did so while experimenting with the code for the solution. With modern IDEs debugging in general can be done without the assistance of printed messages. That said; most production code generates logs which can be used to debug problems and find bottlenecks that should be optimized.
/**
* Test scaffolding.
* This method is not required by the solution.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read values for the linked list ****
String[] vals = sc.nextLine().split("->");
// **** declare the linked list ****
ListNode head = null;
// **** populate the linked list ****
for (int i = 0; i < vals.length - 1; i++) {
int val = Integer.parseInt(vals[i]);
head = insert(head, val);
}
// ???? ????
System.out.print("main <<< head: ");
traverse(head);
System.out.println();
// **** close scanner ****
sc.close();
// **** reverse linked list (use stack) ****
head = reverseStack(head);
// ???? ????
System.out.print("main <<< head: ");
traverse(head);
System.out.println();
// **** reverse linked list (recursive approach) ****
head = reverseList(head);
// ???? ????
System.out.print("main <<< head: ");
traverse(head);
System.out.println();
// **** reverse linked list (use pointers) ****
head = reversePointers(head);
// ???? ????
System.out.print("main <<< head: ");
traverse(head);
System.out.println();
}
This is the test scaffolding I generated. This code is not part of the required solution.
We open a scanner to read the data for the linked list. We generate an array of strings holding the individual values for the linked list including the ‘NULL’ which terminates the linked list. We declare the head for the list and proceed to loop inserting nodes in the specified order.
To make sure we populated the linked list correctly, we display it. After that we close the scanner.
We then call the reverseStack function to reverse the order of the linked list. When done we display the list to make sure all is well. Following we invoke the reverseList to reverse the current linked list. When done we display the results to make sure all is well. Finally we call the reversePointers function to reverse the linked list once again. When done we display the results. Now we can see the reason for the four lines of linked lists in the screen dump of the test.
/**
* Insert node into linked list.
* Recursive function.
*/
static ListNode insert(ListNode head, int val) {
// **** base case ****
if (head == null) {
head = new ListNode(val);
}
// **** recursive case ****
else {
head.next = insert(head.next, val);
}
// **** return linked list ****
return head;
}
This function is used to insert a node into the singly linked list. If the list is empty, our first invocation replaces the head node. Future nodes are inserted at the tail (end) of the list. This is done because the linked list is FIFO data structure. We insert at the tail and remove from the head. This implies that on every insertion we need to traverse the list from the head to the tail. It does not take much to figure out that in production, a “head” and “tail” members in the ListNode class would save a lot of processing. Of course it would also simplify this problem. We would just have to switch the head with the tail and we would be done.
/**
* Traverse linked list.
* Recursive function.
*/
static void traverse(ListNode head) {
// **** base case ****
if (head == null) {
System.out.print("NULL");
return;
}
// **** recursive case ****
else {
System.out.print(head.val + "->");
traverse(head.next);
}
}
This is a recursive function. We could have created an iterative process which would be more efficient than a recursive one. The idea for the traverse function is to check if the head is null (we arrived to the tail of the linked list). In this case we display “NULL”. Otherwise recursively call the function with the next node in the list. Before we call it we display the value for the current node.
/**
* Reverse singly linked list (FIFO).
* Iterative function.
* Uses O(n) space and executes in O(n) time.
*/
static ListNode reverseStack(ListNode head) {
// **** used to reverse the linked list ****
Stack<ListNode> stack = new Stack<ListNode>();
// **** push elements into the stack ****
for (ListNode p = head; p != null; p = p.next) {
stack.push(p);
}
// **** ****
ListNode rll = null;
ListNode tail = null;
// **** pop elements from the stack and append them at the tail ****
while (!stack.empty()) {
// **** ****
ListNode node = stack.pop();
node.next = null;
// **** ****
if (rll == null)
rll = node;
else
tail.next = node;
// **** ****
tail = node;
}
// **** return the reversed linked list ****
return rll;
}
In general when you wish to reverse the order of something a traversal with a stack tends to do the trick. You first traverse the list pushing the nodes into the stack (this is O(n)). Then you pop the values in the stack (this is also O(n)) and adjust the head and next value.
// **** to store the reversed head ****
static ListNode newHead = null;
/**
* Reverse singly linked list.
* Entry for recursive function.
*/
static ListNode reverseList(ListNode head) {
// **** ****
newHead = null;
// **** ****
return reverseRecursive(head, null);
}
We could have implemented the reverseList without the reverseRecursive if we would use a single argument. Since we are using an additional argument we need to have an initialization function followed by a recursive one. Note that we are also using an external variable to update the head of the linked list when we are done.
/**
* Reverse singly linked list.
* Recursive function.
*/
static ListNode reverseRecursive(ListNode head, ListNode prev) {
// **** base case (end of linked list) ****
if (head == null)
return null;
// **** recursive case ****
ListNode temp = reverseRecursive(head.next, head);
// **** save the new head of the list (if needed) ****
if (temp == null)
newHead = head;
// **** update the next element ****
head.next = prev;
// **** return new next or the new head ****
return (prev != null) ? prev : newHead;
}
The reverseRecursive function is used to reverse each node in the linked list. We first look for the tail node (null) and on the way back we update the next member with the value of the previous argument. On the first return, we update the value of the new head. Note that the new head is returned on the last recursive call.
/**
* Reverse singly linked list.
* Use pointers.
*/
static ListNode reversePointers(ListNode head) {
// **** check for empty linked list ****
if (head == null)
return null;
// **** ****
ListNode prev = null;
ListNode nextHead = null;
// **** loop moving the head of the list to the tail ****
while (head != null) {
// **** this will be the next head ****
nextHead = head.next;
// **** to point backwards ****
head.next = prev;
// **** point backwards ****
prev = head;
// **** update the head ****
head = nextHead;
}
// **** return the reversed linked list ****
return prev;
}
This function reverses the linked list iterating from the head to the tail. The function changes pointers as it traverses the tail.
In my humble opinion, in production code, I tend to use doubly linked lists. They are more flexible and you can add class members to facilitate many operations. Of course you will require additional space.
typedef struct SENCOR_QUEUE {
// **** ****
struct SENCOR_QUEUE *next;
struct SENCOR_QUEUE *prev;
unsigned long count;
unsigned long priority;
// **** ****
unsigned long mutex;
__int32 time;
unsigned long signature;
void *privateData;
// **** ****
unsigned long elementSize;
unsigned long maxCount;
// **** for future expansion ****
unsigned char filler[SENCOR_QUEUE_LEN - 40];
} SENCOR_QUEUE;
Note that I am switching programming languages from Java to C. The data structure (not class) contains two pointers, one for the next element and the other for the previous one. This allows our code to traverse the list in a forward or backwards fashion from the head or the tail. Not only that, but we can move in either direction from any element in the list.
Briefly examine the other members. Instead of counting the number of members in the list we can get it in O(1) time. In most production code, 
linked lists need to be protected so they are not accessed simultaneously because their integrity may be violated. A mutex mechanism is something that can be used to protect integrity. A linked list may grow indefinitely. In many cases we might like to enforce a maxim count of elements.
I developed the base data structure many years ago. It has been used in many projects. For performance reasons the data structure and the associated API code was developed using the C programming language. Currently there are several production code using this data structure and associated API calls.
The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 1,699 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
Twitter: @john_canessa