How to Swap Node Pairs In Linked List in Java

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:

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(); } }
Code language: Java (java)

The solution in Java code

Option 1:

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; } }
Code language: Java (java)

Option 2:

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; } }
Code language: Java (java)

Option3:

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; } }
Code language: Java (java)

Test cases to validate our solution

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); } }
Code language: Java (java)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments