Software Engineering

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

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

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

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

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

}