# Reverse a linked list in pairs (alternate pairs of nodes) - Recursive and Iterative

Problem Statement :- Reverse a linked list in such a way that, pair of elements are reversed and linked list internal structure is maintained. Solve using recursive and non-recursive approach.
```Sample Input and Output:-
Inputs:  12 --> 18 -->  172 --> 62 --> 632 --> 192 --> 34
Output:  18 --> 12 -->  62  --> 172 --> 192 --> 632 --> 34
Inputs:  12 --> 18 -->  172 --> 62 --> 632 --> 192
Output:  18 --> 12 -->  62  --> 172 --> 192 --> 632```

#### Recursive implementation - reverse a linked list in pairs

Algorithm:-
1) Reverse pair of nodes of  input list and store references of next pair of nodes using next2nextNode. keep track of previous node using previous reference.
3) Since, previous is storing first node of each pair, so return previous as new head of the list.
4) Check for special cases for empty list and one node list.
```/* Recursive- Reverses the linked list in pairs and returns new head node. */
Node nextNode = null;
Node next2nextNode = null;
Node previous = null;
/* Check for empty and one node list */
if (current == null || current.next == null)
return current;

/* Reverse pair of nodes - check current and current.next is not null */
if (current != null && current.next != null) {
nextNode = current.next;
next2nextNode = nextNode.next;
current.next = previous;
nextNode.next = current;
previous = nextNode;
}
/*
* Recursive call for next pairs and make rest of the list as next of
* first node
*/
if (nextNode != null) {
}

/* Return previous as new head of the input list */
return previous;
}```

#### Iterative approach / Non-recursive implementation - reverse a linked list in pairs

Algorithm:-
1. Check for he null list or one node list, if true return that node.
2. Loop the list, until current node and next node is not null, revert pair of node references(if Node1 - > Node2 it becomes Node2 -> Node1)
3. Update previous reference and head(only first iteration).
4. Finally, check for isolated node, and return modified head.
```/* Iterative- Reverses the linked list in pairs and returns new head node. */
Node nextNode = null;
Node next2nextNode = null;
Node previous = null;

/* Check for empty and one node list */
if (current == null || current.next == null)
return current;

/* Loop rest of the list and reverse pairs of nodes */
while (current != null && current.next != null) {
/* Swap references of two nodes */
nextNode = current.next;
next2nextNode = nextNode.next;
nextNode.next = current;
current.next = next2nextNode;

/*
* Update previous.next and head :- head is updated for first time
* and after that update previous.next to connect next pairs
*/
if (previous == null) {
} else {
previous.next = nextNode;
}

previous = current;
current = next2nextNode;
}
/* Check for isolated node in pairs - when one node is left */
if (current != null) {
previous.next = current;
}
/* Return modified head of the list */
}```

#### Complete sample program - recursive and iterative implementation

```package com.devinline.linkedlist;

/* Recursive- Reverses the linked list in pairs and returns new head node. */
Node nextNode = null;
Node next2nextNode = null;
Node previous = null;
/* Check for empty and one node list */
if (current == null || current.next == null)
return current;

/* Reverse pair of nodes - check current and current.next is not null */
if (current != null && current.next != null) {
nextNode = current.next;
next2nextNode = nextNode.next;
current.next = previous;
nextNode.next = current;
previous = nextNode;
}
/*
* Recursive call for next pairs and make rest of the list as next of
* first node
*/
if (nextNode != null) {
}

/* Return previous as new head of the input list */
return previous;
}

/* Iterative- Reverses the linked list in pairs and returns new head node. */
Node nextNode = null;
Node next2nextNode = null;
Node previous = null;

/* Check for empty and one node list */
if (current == null || current.next == null)
return current;

/* Loop rest of the list and reverse pairs of nodes */
while (current != null && current.next != null) {
/* Swap references of two nodes */
nextNode = current.next;
next2nextNode = nextNode.next;
nextNode.next = current;
current.next = next2nextNode;

/*
* Update previous.next and head :- head is updated for first time
* and after that update previous.next to connect next pairs
*/
if (previous == null) {
} else {
previous.next = nextNode;
}

previous = current;
current = next2nextNode;
}
/* Check for isolated node in pairs - when one node is left */
if (current != null) {
previous.next = current;
}
/* Return modified head of the list */
}

/* Display data of nodes/iterate linked list */
System.out.print("[ ");
while (current != null) {
System.out.print(current.data + " ");
current = current.next;
}
System.out.print(" ]");
} else {
}

}

class Node {
public int data;
public Node next; // reference(handler) for next Node.

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

public static void main(String[] args) {
System.out.println("------1st test-----");
Node node1 = rpll.new Node(12);
Node node2 = rpll.new Node(18);
Node node3 = rpll.new Node(172);
Node node4 = rpll.new Node(62);
Node node5 = rpll.new Node(632);
Node node6 = rpll.new Node(192);
node1.next = node2;
node1.next.next = node3;
node1.next.next.next = node4;
node1.next.next.next.next = node5;
node1.next.next.next.next.next = node6;
System.out.println("Original list is:  12 18 172 62 632 192 19");
+ "(Using Iterative Implementation:) ");

System.out.println("\n------2nd test-----");
Node node12 = rpll.new Node(12);
Node node22 = rpll.new Node(18);
Node node32 = rpll.new Node(172);
Node node42 = rpll.new Node(62);
Node node52 = rpll.new Node(632);
Node node62 = rpll.new Node(192);
Node node72 = rpll.new Node(19);
node12.next = node22;
node12.next.next = node32;
node12.next.next.next = node42;
node12.next.next.next.next = node52;
node12.next.next.next.next.next = node62;
node12.next.next.next.next.next.next = node72;
System.out.println("Original list is:  12 18 172 62 632 192 19");
+ "(Using recursive Implementation:) ");