How to Answer: Given the head of a singly linked list, and return the reversed list.
Advice and answer examples written specifically for a Java Intermediate Level Linked Lists job interview.
2. Given the head of a singly linked list, and return the reversed list.
This interview question concentrates on the developer's skills working with Java linked lists, recursion, and iteration.
Given the head of a singly linked list, reverse the list, and return the reversed list.
/*Example*/
Given: 1 -> 2 -> 3 -> 4 -> 5
Expected output: 5 -> 4 -> 3 -> 2 -> 1Solution:
Approach I (Recursive):
We maintain the current node and the node next to this node.
In our reverse() function we are taking the current node and the previous node as the input arguments. It reverses a singly linked list.
We continue to call the function with the node next to the head as the current node and the head as the previous node till we have reached the last node.
For 1 -> 2 -> 3 once we have reached the last node it would look like 1 -> 2 -> 3 -> null. Thus we need to make the last node point to the second last node. Which will make the list as 1 -> 2 <- 3.
Going back through our recursive calls we do the same reversing and return the last node as the root in the end.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(head, null);
}
public ListNode reverse(ListNode head, ListNode previous) {
if(head == null) return null;
ListNode curr = head;
if (head.next != null) {
curr = reverse(head.next, head);
}
head.next = previous;
return curr;
}
}Time complexity- O(n) where n is the length of the list
Space complexity- O(n)
Approach II (Iterative):
We wish to maintain three variables. current, next, and prev.
During every iteration, we copy the node next to the head into our next variable. We need to save this before we move forward and reverse the current node.
Then we make the head node point to the previous node. With this, we are reversing our current node to point to the previous node.
Next, we assign the prev variable to the current node. Thus when we iterate forward in our list the node next to this can be pointed to this.
Finally, we assign the next to the current node so that we can iterate forward in our list and repeat the process for the next nodes.
Once we are done with all of the iterations we notice that the head variable is pointing to nothing. Thus we swap its value with the prev variable.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
class Solution {
public ListNode reverseList(ListNode head) {
ListNode current = head;
ListNode next = head;
ListNode prev = null;
while (current != null) {
// Store next
next = current.next;
// Reverse current node's pointer
current.next = prev;
// Move pointers one position ahead.
prev = current;
current = next;
}
head = prev;
return head;
}
}Time complexity- O(n) n is the length of the list
Space complexity- O(1)
Written by S. Kumar on May 22nd, 2021