Reverse a Linked List – Interview Question

Reverse a Linked List – Interview Question

September 9, 2020 Uncategorized 0


Given a singly linked list, reverse it.

Let’s find out how to answer this question in a technical interview.

Suppose Here is the list:

 

 

And here is how the output should look like:

A linked list node has 2 components: the value and the reference to the next node.

public class Node
{
  public int Value { get; set; }
  public Node Next { get; set; }
}

You are given the head of a linked list which points to the first node. And then each node’s next points to the next node.

So the tricky part here is, if you say change Node 2 to point to Node 1 and you have not saved the reference to Node 3 then there is no way you can reach Node 3. So you have to keep those references saved in temporary variables to successfully answer this question.

So in the code, we will run a while loop, and change the reference such that node2’s next will be node1 instead of node3 and save reference to Node3. The while loop will look something like this:

Node prev = null;
Node curr = head;
while (curr != null)
{
  Node temp = curr.Next;
  curr.Next = prev;
  prev = curr;
  curr = temp;
}
return prev;

Next, let’s discuss the edge cases.
Please make sure you take care of scenarios where the list size is 0 or 1.

With edge cases of zero or one, the code will look something like this.

if (head == null)
  return null;
if (head.Next == null)
  return head;
Node prev = null;
Node curr = head;
while (curr != null)
{
  Node temp = curr.Next;
  curr.Next = prev;
  prev = curr;
  curr = temp;
}
return prev;

As always, I have posted this code on GitHub and here is the Link. I will recommend you to try it on your own before downloading the code and looking at the solution.

Now, real quick, here is a brain teaser:

What did a single linked list say to a circular linked list that made the circular list really mad?

It’s time to get your head out of your ass 😉

Adding humor to your interview can also help you achieve success in getting the job. Of course you should know the answer to your technical questions. But along with that, if you are funny, you can increase your probability of cracking the interview. I talk about this concept in my book as well – Mastering the Web Developer Interview.

This book is available in paperback/ ebook and audio format.

I will be posting more such questions and their solutions on this channel. So do not forget to subscribe.
Until then, Happy Coding 🙂