## Tuesday 13 February 2018

### Java Program to Reverse a Linked List using Recursion and Loops

In previous post, we learned about Internal working of LinkedList in Java. In this, we can write a code to reverse a linkedlist using recursion and iterative way.

``` package com.practice;

public class ReverseLinkedList {

static class Node {

int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

// using iterative way
Node reverse(Node node) {
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}

// using recursive
Node reverseUtil(Node curr, Node prev) {
if (curr.next == null) {

curr.next = prev;
return null;
}

Node next1 = curr.next;

/* and update next ..*/
curr.next = prev;

reverseUtil(next1, curr);
}

// prints content of linked list
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}

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

System.out.println("Original Linked list ");
Node res = list.reverseUtil(head, null);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(res);

System.out.println("");
System.out.println("Original Linked list2 ");
Node result = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list2 ");
list.printList(result);
}
}
```

Output:--   Original Linked list
1 2 3 4
4 3 2 1
4 3 2 1