A common algorithm question is “How to Reverse a Linked List”. Below the SimpleLinkedList (Java) class contains a simple example to follow.

The class SimpleLinkedList contains one field, head, which is used to keep track of the head (first) node of the linked list.

public class SimpleLinkedList {

    public static Node head;
...

The nested class Node is the class used to create nodes (items) contained in the linked list. Each node contains a reference to the next node in the list, stored in the next variable.

public static class Node {
  public int data;
  public Node next = null;

  public Node(int data) {
    this.data = data;
  }
}

The main method illustrates how to add items to a SimpleLinkedList object, as well as call the reverse method on that object.

public static void main(String[] args){
    SimpleLinkedList ll = new SimpleLinkedList();
    ll.head = new Node(1);
    ll.head.next = new Node(2);
    ll.head.next.next = new Node(3);
    ll.head = ll.reverse();
}

The reverse method works by using a loop to visit each node in the linked list. For each iteration of the loop, the curr, prev, and next local variables are used take a node’s next, and make it the node’s previous. For example, the first node has no previous node. The first node’s previous will become the original second node, while the first node’s next will become null (making it the last node). The head node of the newly reversed linked list is returned to make it possible to assign this as the new head of the SimpleLinkedList object.

public Node reverse(){
    if(head.next == null) return head;
    Node curr = head;
    Node prev = null;
    Node next = null;

    while(curr != null) {
       next = curr.next;
       curr.next = prev;
       prev = curr;
       curr = next;
    }
        return prev;
}

The full example is shown below as well as on the Big Datums GitHub repo.

package com.bigdatums.interview;

public class SimpleLinkedList {

    public static Node head;

    public static class Node {
        public int data;
        public Node next = null;

        public Node(int data) {
            this.data = data;
        }
    }

    public Node reverse(){
        if(head.next == null) return head;
        Node curr = head;
        Node prev = null;
        Node next = null;

        while(curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public void printList(){
        Node curr = head;
        while(curr != null) {
            System.out.println(curr.data);
            curr = curr.next;
        }
    }

    public static void main(String[] args){
        SimpleLinkedList ll = new SimpleLinkedList();
        ll.head = new Node(1);
        ll.head.next = new Node(2);
        ll.head.next.next = new Node(3);
        ll.head = ll.reverse();
        ll.printList();
    }

}