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 Nodes 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);
}
}
|
