Swap Kth node from beginning with Kth node from end in a Linked List

Question

Given a singly linked list, swap kth node from beginning with kth node from end. Swapping of data is not allowed, only pointers should be changed.

This code is attributed to geeksforgeeks. I'm looking for code-review, optimizations and best practices.

1. Why I don't extend or reuse: I am prepping for interviews, and interviewers explicitly want you to code, in my experience. I request the reviewer to not insist on reusing, as I am aware in real life reusability is the right approach. This does not work in interviews.

2. Why don't I use a Util class instead nesting method inside linked list? That is because I need the Node to be an internal data structure. Had I made a Util class, it would have no access to internal data structure and perform operations on the node's pointers.

public class SwapKth<T> {

    private Node<T> first;
    private int size;

    public SwapKth(List<T> items) {
        addAll(items);
    }

    private void addAll(List<T> items) {
        Node<T> prev = null;
        size = items.size();
        for (T item : items) {
            Node<T> node = new Node<T>(item);
            if (prev == null) {
                first = prev = node;
            } else {
                prev.next = node;
                prev = node;
            }
        }
    }

    private static class Node<T> {
        private Node<T> next;
        private T item;

        Node(T item) {
            this.item = item;
        }
    }

    public void swap (int n)  {
        if (n == 0) {
            throw new IllegalArgumentException("The value of n should be greater than 0.");
        }
        if (n > size) {
            throw new IllegalArgumentException("The value of n: " + n + " is greater than: " + size);
        }

        // code to reach the nth node from front.
        Node<T> x = first;
        Node<T> prevX = null;
        for (int i = 0; x != null && i < (n - 1); x = x.next, i = i + 1) {
            prevX = x;
        }

        // code to reach the nth node from the end.
        Node<T> temp = x.next;  // note: we have x.next in place.
        Node<T> y = first; 
        Node<T> prevY = null;
        for (; temp != null; temp = temp.next, y = y.next) {
            prevY = y;
        } 

        // if 'x' and 'y' happen to be the same node.
        // eg: 1->2->3->4->5, swap 3rd from start with 3rd from the end.
        if (x == y) return;


        Node<T> prevFirst = null;
        Node<T> first = null;
        Node<T> prevSecond = null;
        Node<T> second = null;


        if (n <= size/2) { 
            prevFirst =  prevX; 
            first =  x;
            prevSecond = prevY; 
            second =  y;
        } else {
            prevFirst =  prevY;
            first =  y;
            prevSecond = prevX;    
            second = x;
        }



        if (first.next == second) {
            adjacentSwap(prevFirst, first, second);  
        } else {
            distantSwap(prevFirst, first, prevSecond, second);  
        }

    }


    /**
     * Swap 3rd from start with 3rd form the end, in a linkedlist like.
     * 1->2->3->4->5->6
     * Here node 3, and 4 are adjacent
     * 
     * Edge case:  
     * 1->2          (swap 1 with 2)
     */
    public void adjacentSwap(Node<T> firstPrev, Node<T> first, Node<T> second) {
        first.next = second.next;
        second.next = first;
        if (firstPrev != null) {
            firstPrev.next = second;
        } else {
            this.first = second;
        }
    }



    /**
     * Swap 2nd not from the front and 2nd node from the end.
     * 1->2->3->4->5->6
     * Here node 2nd node and 5th node are not adjacent
     * 
     * Edge case:
     * 1->2->3->4->5->6 (swap 1 with 6)
     * 
     */
    public void distantSwap(Node<T> firstPrev, Node<T> first, Node<T> secondPrev, Node<T> second) {
        if (firstPrev != null) {
            firstPrev.next = first.next;
            secondPrev.next = second.next;

            second.next = firstPrev.next;
            first.next = secondPrev.next;

            firstPrev.next = second;
            secondPrev.next = first;
        } else {
            secondPrev.next = second.next;

            second.next = first.next;
            first.next = secondPrev.next;

            this.first = second;
            secondPrev.next = first;
        }
    }

    // size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
    public List<T> toList() {
        final List<T> list = new ArrayList<>();
        if (first == null) return list;

        for (Node<T> x = first; x != null; x = x.next) {
            list.add(x.item);
        }

        return list;
    }


    @Override
    public int hashCode() {
        int hashCode = 1;
        for (Node<T> x = first; x != null; x = x.next)
            hashCode = 31*hashCode +  (x.item == null ? 0 : x.hashCode());
        return hashCode;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SwapKth<T> other = (SwapKth<T>) obj;
        Node<T> currentListNode = first; 
        Node<T> otherListNode =  other.first;

        while (currentListNode != null && otherListNode != null) {
            if (currentListNode.item != otherListNode.item) return false;
            currentListNode = currentListNode.next;
            otherListNode = otherListNode.next;
        }
        return currentListNode == null && otherListNode == null;
    }
}


public class SwapKthTest {

    @Test
    public void testEvenLength() {
        SwapKth<Integer> sk1 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        sk1.swap(1);
        assertEquals(Arrays.asList(6, 2, 3, 4, 5, 1), sk1.toList());

        SwapKth<Integer> sk2 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        sk2.swap(2);
        assertEquals(Arrays.asList(1, 5, 3, 4, 2, 6), sk2.toList());

        SwapKth<Integer> sk3 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        sk3.swap(3);
        assertEquals(Arrays.asList(1, 2, 4, 3, 5, 6), sk3.toList());

        SwapKth<Integer> sk4 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        sk4.swap(4);
        assertEquals(Arrays.asList(1, 2, 4, 3, 5, 6), sk4.toList()); 

        SwapKth<Integer> sk5 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        sk5.swap(5);
        assertEquals(Arrays.asList(1, 5, 3, 4, 2, 6), sk2.toList());

        SwapKth<Integer> sk6 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6));
        sk6.swap(6);
        assertEquals(Arrays.asList(6, 2, 3, 4, 5, 1), sk6.toList()); 
    }

    @Test
    public void testOddLength() {
        SwapKth<Integer> sk7 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        sk7.swap(1);
        assertEquals(Arrays.asList(5, 2, 3, 4, 1), sk7.toList());

        SwapKth<Integer> sk8 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        sk8.swap(2);
        assertEquals(Arrays.asList(1, 4, 3, 2, 5), sk8.toList());

        SwapKth<Integer> sk9 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        sk9.swap(3);
        assertEquals(Arrays.asList(1, 2, 3, 4, 5), sk9.toList());

        SwapKth<Integer> sk10 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        sk10.swap(4);
        assertEquals(Arrays.asList(1, 4, 3, 2, 5), sk10.toList());

        SwapKth<Integer> sk11 = new SwapKth<Integer>(Arrays.asList(1, 2, 3, 4, 5));
        sk11.swap(5);
        assertEquals(Arrays.asList(5, 2, 3, 4, 1), sk11.toList());
    }

    @Test
    public void testTwoElement() {
        SwapKth<Integer> sk12 = new SwapKth<Integer>(Arrays.asList(1, 2));
        sk12.swap(1);
        assertEquals(Arrays.asList(2, 1), sk12.toList()); 

        SwapKth<Integer> sk13 = new SwapKth<Integer>(Arrays.asList(1, 2));
        sk13.swap(2);
        assertEquals(Arrays.asList(2, 1), sk13.toList()); 
    }

    @Test
    public void testSingleElement() {
        SwapKth<Integer> sk14 = new SwapKth<Integer>(Arrays.asList(1));
        sk14.swap(1); 
        assertEquals(Arrays.asList(1), sk14.toList()); 
    }

}

Answer 1

Realize that when \$n > size / 2\$, it's equivalent to \$n = size - n + 1\$. That is, in a list of 6 elements, swapping with n=6 should be the same as n=1. As a result, this code can be simplified:

Node<T> prevFirst = null;
Node<T> first = null;
Node<T> prevSecond = null;
Node<T> second = null;

if (n <= size/2) { 
    prevFirst =  prevX; 
    first =  x;
    prevSecond = prevY; 
    second =  y;
} else {
    prevFirst =  prevY;
    first =  y;
    prevSecond = prevX;    
    second = x;
}

if (first.next == second) {
    adjacentSwap(prevFirst, first, second);  
} else {
    distantSwap(prevFirst, first, prevSecond, second);  
}

To this:

if (n > size / 2) {
    n = size - n + 1;
}

// ... the code finding `prevX`, `x`, `prevY`, `y`, `prevY`

if (x.next == y) {
    adjacentSwap(prevX, x, y);
} else {
    distantSwap(prevX, x, prevY, y);
}

---

This loop can be simplified a bit:

for (int i = 0; x != null && i < (n - 1); x = x.next, i = i + 1) {
    prevX = x;
}

You don't need the null check on x, thanks to the validation on n with respect to size at the beginning of the method. Also you should write ++i instead of i = i + 1, and no need for the parentheses in i < (n - 1):

for (int i = 0; i < n - 1; x = x.next, ++i) {
    prevX = x;
}

---

In this code, you're effectively iterating from the beginning until the size - n + 1-th node.

Node<T> temp = x.next;  // note: we have x.next in place.
Node<T> y = first; 
Node<T> prevY = null;
for (; temp != null; temp = temp.next, y = y.next) {
    prevY = y;
}

But you don't have to: you have already iterated until the n-th, and to reach the \$(size - n + 1)\$-th node, you only need to iterate over \$size - 2 * n + 1\$ items, which can be far less than going from the beginning:

Node<T> y = x;
Node<T> prevY = null;
for (int i = 0; i < size - 2 * n + 1; ++i, y = y.next) {
    prevY = y;
}

Answer 2

Not mentioned elsewhere:

Dial back on the excessive use of new lines. Readability is important but remember that scrolling impairs readability as well so try to keep your code a bit tighter (but not too tight!).

Why are adjacentSwap and distantSwap public functions? You're not testing them in the unit tests and they make no sense to be public to me.

I believe that you should extract the node finding in the swap method to functions.