Reversing a Linked List

A Linked List is a data structure that consists of nodes that points to another node, hence the name. The anatomy of a Linked List is that of a head, which is the first node, and a tail, which is the last node. So with that being said, how do you reverse a Linked List? Think of it like this.

Let's Review the Antamoy of a Linked List and Its Basic Functions

So we know this linear data structure consists of nodes, with each node made up of a value and a pointer. The head(1st node) is pointing to another, and the head's next node is pointing to another node and this continues for each following node until the tail(nth/last) has no node, which is a null value.

Traversing through a linked list from head to tail requires initializing a new node with the value of head and repeatedly keep assigning this new node(a copy of head) to the node it is pointing to until it reaches the tail.

Reversing a Linked List

So how would we reverse a linked list? We would need to traverse through the linked list like we normally would while also pointing to the previous node. Take a look at the pseudocode.

Pseudocode

reverseList(head):
  # Initialize previous node to null
  previous = None

  # Initialize current node to head
  current = head

  # While current node is not null
  while current is not None:
    # Store next node in a temporary variable
    next = current.next
    # Reverse the link between the current node and the next node
    current.next = previous
    # Move previous node one step forward
    previous = current
    # Move current node one step forward
    current = next

  # Return previous node, which is now the head of the reversed linked list
  return previous

As we traverse through the linked list, we store our current's next node temporarily, the current's next pointer is now assigned to our previous node, our previous node is now equal to our current node and our current node is now equal to the node that it was originally pointing to, which has one less node.

Java:

public class ReverseLinkedList {

  public static Node reverseList(Node head) {
    Node previous = null;
    Node current = head;
    Node next = null;

    while (current != null) {
      next = current.next;
      current.next = previous;
      previous = current;
      current = next;
    }

    return previous;
  }

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

    Node reversedHead = reverseList(head);

    System.out.println("Original linked list:");
    printLinkedList(head);

    System.out.println("Reversed linked list:");
    printLinkedList(reversedHead);
  }

  private static void printLinkedList(Node head) {
    while (head != null) {
      System.out.print(head.value + " ");
      head = head.next;
    }
    System.out.println();
  }
}

class Node {

  int value;
  Node next;

  public Node(int value) {
    this.value = value;
    next = null;
  }
}

C++

Node* reverseList(Node* head) {
  Node* previous = nullptr;
  Node* current = head;
  Node* next;

  while (current != nullptr) {
    next = current->next;
    current->next = previous;
    previous = current;
    current = next;
  }

  return previous;
}

Python:

def reverseList(head):
  previous = None
  current = head

  while current is not None:
    next = current.next
    current.next = previous
    previous = current
    current = next

  return previous;