# Reverse a linked list

Published , updated
Tags:

This article looks at the interview question - Reverse a linked list.

Whenever an interviewer asks this question, or any question on linked lists, there is something you should ask before doing anything;

Is it a singly linked list of a doubly linked list?

Most often than not it will likely be singly linked list since they generally lead to the more compelling problems, but you need to ask or you could solve the wrong problem. This article will present solutions for both data structures.

## Singly linked list

### Analysis

Let’s start off by defining the data structure:

public class LinkedList {
public int data;
}


Linked list questions always seem simple, but when you get into dealing with the pointers it’s easy to get lost. I recommend drawing a picture of the pointers, that way if you do get confused you can always refer to it.

The most important thing in this problem is to make sure the head and tail pointers are handled. Notice in the image how the old head’s next point will be null whereas the new head is no longer null. The main section of the function will involve flipping the pointer between elements the other way.

Just remember if you ever get lost, go back to the picture.

### Pseudocode

function reverseSingly (head)
if head is null
return null
prev ← null
while head.next is not null
return head

### Code

public static LinkedList reverseSingly(LinkedList head) {
if (head != null) {
LinkedList prev = null;
while (head.next != null) {
}
}
}
function reverseSingly(head) {
var prev;
var next = head.next;
}
}

function SinglyLinkedList(data, next) {
this.data = data;
this.next = next;
}

## Doubly linked list

### Analysis

Again, let’s define the data structure:

public class LinkedList {
public int data;
}


Now draw the picture:

It becomes clear from the picture that the list can be reversed by simply swapping each node’s next and prev pointers. The only part that could be tricky with this question is ensuring that the new head pointer is valid and doesn’t introduce a cycle.

### Pseudocode

function reverseDoubly (head)
if head is null
return null

loop {
if head.prev is null
}

### Code

public static LinkedList reverseDoubly(LinkedList head) {
while (head != null) {
if (temp == null)
break;
}
}
function reverseDoubly(head) {
while (head != null) {
var temp = head.next;
if (!temp) {
break;
}
}
}

function DoublyLinkedList(data, next) {
this.data = data;
this.next = next;
if (this.next) {
this.next.prev = this;
}
this.prev = undefined;
}

## Textbooks

Here are two textbooks that provide many Q&A's like this post that I personally recommend, both were invaluable to me when I was studying for my interviews.