- Implement multiple pointers with linked lists
- Implement recursion with linked lists
- White Board Practice / Technical Communication
Write a function that takes in the head of a Singly Linked List, reverses the list in place (does not create a new list), and returns its new head.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to null if the tail of the list.
You can assume that the input Linked List will always have at least one node.
Feel free to provide this example to your interviewer:
Input: 0 -> 1 -> 2 -> 3 -> 4 -> 5 // the head node has the value 0
Output: 5 -> 4 -> 3 -> 2 -> 1 -> 0 // the value of the head node is now 5 - This would be a great problem to have your interviewee use a white board.
- The interviewee should conceptionally explain to you how to reverse the linked list. They do not have to code a linked list from scratch. Instead the expectation is for them to walk you through what steps would be necessary to reverse a list that is already created. This is a great opportunity for your interviewee to practice psudeo coding, white boarding and technical communication.
- Your interviewee does not need to focous on edge cases for this problem. It does not matter if the node values are in sorted, only that whatever order they are inputed returns reversed at output.
- If your interviewee asks what happens if the head node is null direct them to the last line of the prompt. "You can assume that the input Linked List will always have at least one node." - meaning the head node will never be null.
- If your interviewee does not have a white board application of choice feel free to direct them here
- If you interviewee is stuck provide them with a hint that they may need to manipulate three nodes at once as they move threw each step.
- You can not use .prev in a singly linked list; only .next is available. If your interviewee does not know that already, try to lead them there without directly telling them.
If you decide you want to walk your interviewee threw the problem with code and not using a whiteboard here is the starter code needed:
class LL {
constructor(value) {
this.value = value;
this.next = null
}
}
let head = new LL(0)
head.next = new LL(1)
head.next.next = new LL(2)
head.next.next.next = new LL(3)
console.log(head) //for before reversal - input 0->1->2->3
---
console.log(reverseLinkedList(head)) //for after the function is invoked - output 3<-2<-1<-0function reverseLinkedList(head) {
//Initialize pointers
let prev = null;
let current = head; // where we are at with every move
let next = null;
//When the current is null we are past the linked list's tail
while(current !== null){
//Stashes the next value for us - captures it temporarily
next = current.next;
//Where the reversal happens
current.next = prev;
//Order is important! This is a linked list - we always want to have connection to each node, so we are stashing each node before we overwrite it
prev = current;
current = next;
}
//Breaks out of while loop. If the current is null, the previous is the final node that has a value. The new head.
return prev;
}- Time Complexity: 0(n)
- Space Complexity: 0(1)
function reverseLinkedList(head) {
if(!head || !head.next) return head;
const next = head.next;
const newHead = reverseLinkedList(next);
next.next = head;
head.next = null;
return newHead;
}- Time Complexity: 0(n)
- Space Complexity: 0(n)
function reverseLinkedList(head) {
if (head.next === null) return head;
let tail = swap(head, head.next);
head.next = null;
return tail;
};
const swap = function(head, tail) {
let temp = tail.next;
tail.next = head;
if(temp) {
tail = swap(tail, temp);
}
return tail;
}- Time Complexity: 0(n)
- Space Complexity: 0(n)