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.
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.
Why don't I use a
Util
class instead nesting method inside linked list? That is because I need theNode
to be an internal data structure. Had I made aUtil
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());
}
}