Monthly Archives: August 2016

In-place Reversing a LinkedList effificiently

A LinkedList can be reversed in different ways. But reversing in-place, i.e changing the direction is the most efficient way in my opinion. Because it does not take extra space to store the nodes.

Below the code how to achieve it:

class Node {
  Node next = null;
  int data;
  
  public Node (int data) {
    this.data = data;
  }
  
  public void addToTail(int data) {
    Node newNode = new Node(data);
    
    Node n = this;
    
    while (n.next != null) {
      n = n.next;
    }
    n.next = newNode;
  }
  
  public String toString() {
    return data + "";
  }
}

public class LinkedList {
    /**
    * Print the linked list
    */
    private static void printLL(Node n) {
        while (n != null) {
            System.out.print(n.data);
            if (n.next != null)
                System.out.print(" -> ");

            n = n.next;
        }
    }

     /**
     * Reverse the linked list
     * @param head
     * @return new head
     */ 
    public static Node reverse(Node head) {
        Node prev = null;
        Node current = head;

        while (current != null) {
            Node temp = current.next;
            current.next = prev;

            prev = current;
            current = temp;
        }

        return prev;
    }

    public static void main(String[] s) {
        Node ll = new Node(3);
        ll.next = new Node(4);
        ll.next.next = new Node(5);
        ll.next.next.next = new Node(3);
        ll.next.next.next.next = new Node(1);
        Node reverseList = reverse(ll);
        printLL(reverseList);
    }
}

Output will be:

1 -> 3 -> 5 -> 4 -> 3