## The challenge

If you are given the head node in a linked list, write a method that swaps each pair of nodes in the list, then returns the head node of the list.

Example:

if you are given a list ordered `A,B,C,D` the resulting list should be `B,A,D,C`.

The list will be composed of `Node`s of the following specification:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````public class Node { private String value; public Node next; public Node(String value) { this.value = value; } public String getValue() { return value; } public String toString() { return this.value; } public String printList() { if (this.next == null) return this.toString() + " ->"; return this.toString() + " -> " + next.printList(); } } ``````

## The solution in Java code

Option 1:

 ``````1 2 3 4 5 6 7 8 `````` ``````public class LinkedListPairs { public static Node swapPairs(Node head) { if (head == null || head.next == null) return head; Node a = head, b = head.next, c = b.next; b.next = a; a = b; b = a.next; b.next = swapPairs(c); return a; } } ``````

Option 2:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````public class LinkedListPairs { public static Node swapPairs(Node head) { if (head == null || head.next == null) return head; Node next = head.next; head.next = swapPairs(next.next); next.next = head; return next; } } ``````

Option3:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 `````` ``````public class LinkedListPairs { public static Node swapPairs(Node head) { Node prev = new Node("temp"); prev.next = head; Node result = prev; Node first = head; while (first != null && first.next != null) { Node second = first.next; // Swap Pair prev.next = second; first.next = second.next; second.next = first; // Update Pointers prev = first; first = first.next; } return result.next; } } ``````

## Test cases to validate our solution

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 `````` ``````import org.junit.Test; import static org.junit.Assert.*; public class LinkedListPairsTest { @Test public void basicTests() { executeTest(null, LinkedListPairs.swapPairs(null)); executeTest(new Node("A"), new Node("A")); executeTest(new ListBuilder().withValue("B").withValue("A").withValue("D").withValue("C").build(), new ListBuilder().withValue("A").withValue("B").withValue("C").withValue("D").build()); } // use this to build your own tests private class ListBuilder { private Node head = null, last = null; public ListBuilder withValue(String value) { if (head == null) { head = new Node(value); last = head; } else { last.next = new Node(value); last = last.next; } return this; } public Node build() { return head; } } private static void executeTest(Node input, Node expectedResult) { Node output = LinkedListPairs.swapPairs(input); if (expectedResult == null) { assertNull(output); return; } final String expected = expectedResult.printList(); final String actual = output.printList(); final String errMsg = "Expected '" + expected; assertEquals(errMsg, expected, actual); } } ``````