content: package linkedlist;
  
  
  public class ReverseLinkedList {
  
      /*
       * Runtime Complexity:
       * Linear, O(n).
       * As we can reverse the linked list in a single pass.
       *
       * Memory Complexity:
       * Constant, O(1).
       * As no extra memory is required for the iterative solution.
       * */
  
      private static class LinkedList {
  
          private LinkedList.Node head;
          public Node reverse(Node node) {
              Node previous = null;
              Node current = node;
              Node next = null;
  
              while (current != null) {
                  next = current.next;
                  current.next = previous;
                  previous = current;
                  current = next;
              }
              node = previous;
              return node;
          }
  
  
          public void printList(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
          }
  
          public static class Node {
  
              private int data;
              private Node next;
  
              public Node(int data) {
                  this.data = data;
                  this.next = null;
              }
          }
      }
  
  
      public static void main(String [] args) {
  
          LinkedList linkedList = new LinkedList();
          linkedList.head = new LinkedList.Node(1);
          linkedList.head.next =  new LinkedList.Node(2);
          linkedList.head.next.next =  new LinkedList.Node(3);
          linkedList.head.next.next.next = new LinkedList.Node(4);
  
          linkedList.printList(linkedList.head);
          linkedList.head = linkedList.reverse(linkedList.head);
          System.out.println("");
          linkedList.printList(linkedList.head);
      }
  }
  