Growing with the Web

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.

Singly linked list being reversed

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:

Doubly linked list being reversed

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;
}

Comments

comments powered by Disqus
Like this article?
Subscribe for more!