# 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;
public LinkedList next;
}


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
head.next ← prev
prev ← head
head ← old value of head.next
head.next ← prev
return head

### Code

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

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;
public LinkedList next;
public LinkedList prev;
}


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 {
swap head.next and head.prev values
if head.prev is null
return head
head ← head.prev
}

### Code

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

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.

Like this article?
Subscribe for more!