6
\$\begingroup\$

Here is the source of the question: GitHub

Given a singly linked list, swap the list items in pairs (reconnect the pointers, not simply swap the values). For example:

Before: A->B->C->D

After: B->A->D->C

See the method reversePairs.

Node

class Node {

    private Node next;
    private int data;

    public Node(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node getNext() {
        return next;
    }

    @Override
    public String toString() {
        return Integer.toString(data);
    }

}

SinglyLinkedList

public class SinglyLinkedList {

    private Node mFirst;
    private Node mLast;

    public SinglyLinkedList(Node first) {
        this.mFirst = first;
        this.mLast = first;
    }

    public SinglyLinkedList(int []array) {
        if (array == null || array.length == 0) {
            throw new IllegalArgumentException();
        }
        this.mFirst = new Node(array[0]);
        this.mLast = this.mFirst;
        for (int i = 1; i < array.length; i++) {
            addLast(new Node(array[i]));
        }
    }

    public void addLast(Node node) {
        mLast.setNext(node);
        mLast = node;
    }

    public Node getFirst() {
        return mFirst;
    }

    public Node getLast() {
        return mLast;
    }

    public void print() {
        Node current = mFirst;
        System.out.print("[");
        while (current != null) {
            System.out.print(current);
            current = current.getNext();
            if (current != null) {
                System.out.print(", ");
            }
        }
        System.out.print("]");
        System.out.println();
    }

    public void reversePairs() {
        Node prev = mFirst;
        Node curr = prev.getNext();
        Node old = null;
        while (curr != null) {
            Node next = curr.getNext();
            curr.setNext(prev);
            prev.setNext(null);
            if (prev == mFirst) {
                mFirst = curr;
            }
            if (old != null) {
                old.setNext(curr);
            }
            old = prev;
            prev = next;
            if (prev != null) {
                curr = prev.getNext();
                if (curr == null) {
                    old.setNext(prev);
                    mLast = prev;
                }
            } else {
                mLast = old;
                break;
            }
        }
    }
}

Testing:

package com.reversell;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class SinglyLinkedListTest {

    private int[] single = new int[] {
            12
    };

    private int[] twoElems = new int[] {
            12, 34
    };
    private int[] twoElemsReversedPairs = new int[] {
            34, 12
    };

    private int[] threeElems = new int[] {
            12, 34, 78
    };
    private int[] threeElemsReversedPairs = new int[] {
            34, 12, 78
    };

    private int[] evenElems = new int[] {
            12, 34, 78, 124
    };
    private int[] evenElemsReversedPairs = new int[] {
            34, 12, 124, 78
    };

    private int[] oddElems = new int[] {
            12, 34, 78, 45, 90
    };
    private int[] oddElemsReversedPairs = new int[] {
            34, 12, 45, 78, 90
    };

    @Test
    public void test() {
        assertEquals(true, doReverse(new SinglyLinkedList(single), single, single));

        assertEquals(true, doReverse(new SinglyLinkedList(twoElems), twoElems, twoElemsReversedPairs));

        assertEquals(true, doReverse(new SinglyLinkedList(threeElems), threeElems, threeElemsReversedPairs));

        assertEquals(true, doReverse(new SinglyLinkedList(oddElems), oddElems, oddElemsReversedPairs));

        assertEquals(true, doReverse(new SinglyLinkedList(evenElems), evenElems, evenElemsReversedPairs));

    }

    private boolean isFirstCorrect(SinglyLinkedList linkedList, int value) {
        return linkedList.getFirst().getData() == value;
    }

    private boolean isLastCorrect(SinglyLinkedList linkedList, int value) {
        return linkedList.getLast().getData() == value;
    }

    private boolean doReverse(SinglyLinkedList list, int[] origArray, int[] reversedArray) {
        boolean checkOrig = isListCorect(list, origArray);
        if (!checkOrig) {
            return false;
        }
        list.reversePairs();

        return isFirstCorrect(list, reversedArray[0]) && isLastCorrect(list,
                reversedArray[reversedArray.length - 1]) && isListCorect(list, reversedArray);
    }

    private boolean isListCorect(SinglyLinkedList list, int[] array) {
        Node curr = list.getFirst();
        int arrayIndex = 0;
        while (curr != null) {
            if (array[arrayIndex] != curr.getData()) {
                return false;
            }
            curr = curr.getNext();
            arrayIndex++;
        }
        return true;
    }

}
\$\endgroup\$
9
\$\begingroup\$

Simpler implementation

The implementation is a bit confusing:

  • Variable names like prev and old have too similar meanings, which makes it hard to follow what they are referring to

  • The check prev == mFirst in every loop cycle is redundant: the condition will only be true near the head of the list

In addition, the current implementation doesn't handle the case of an empty list.

I propose this alternative, simpler implementation:

public void reversePairs() {
    Node sentinel = new Node(0);
    sentinel.setNext(mFirst);

    Node node = sentinel;
    while (true) {
        Node next = node.getNext();
        if (next == null || next.getNext() == null) {
            break;
        }
        node.setNext(swap(next));
        node = next;
        mLast = next;
    }

    mFirst = sentinel.getNext();

    if (mLast.getNext() != null) {
        mLast = mLast.getNext();
    }
}

private Node swap(Node node) {
    Node next = node.getNext();
    Node nextnext = next.getNext();
    node.setNext(nextnext);
    next.setNext(node);
    return next;
}

Note that this can be even more simple if you can let go of the mLast field: you could simply remove all the references to mLast from the above. I don't think mLast is very useful in a singly linked list.

Unit testing

The way you test the implementation is convoluted, hard to follow, because you are violating many good practices of unit testing:

  • Test methods should:
    • test just one thing
    • be short
    • be simple
    • communicate clearly the inputs, expected outputs, and the causality relationship between the two
  • A test class should not have non-trivial logic (who will test the test?)

Consider this alternative implementation for the test cases:

@Test
public void test_12_reversed_is_12() {
    assertArrayEquals(new int[]{12}, reversed(12));
}

@Test
public void test_12_34_reversed_is_34_12() {
    assertArrayEquals(new int[]{34, 12}, reversed(12, 34));
}

@Test
public void test_12_34_78_reversed_is_34_12() {
    assertArrayEquals(new int[]{34, 12, 78}, reversed(12, 34, 78));
}

@Test
public void test_12_34_78_124_reversed_is_34_12_124_78() {
    assertArrayEquals(new int[]{34, 12, 124, 78}, reversed(12, 34, 78, 124));
}

Notice that:

  • The input and expected outputs are perfectly clear, and so is each test case
  • Using assertArrayEquals instead of assertEquals(true, ...) produces much more readable output in case of a failure. assertEquals(true, ...) will only tell you that something was not true, without giving you more hints to debug. assertArrayEquals will tell you the mismatched values.

reversed is a helper method to facilitate simple test cases:

private int[] reversed(int... nums) {
    SinglyLinkedList list = new SinglyLinkedList(nums);
    list.reversePairs();
    return toArray(list);
}

toArray is another helper that perhaps should be part of SinglyLinkedList itself:

private int[] toArray(SinglyLinkedList list) {
    List<Integer> values = new ArrayList<>();

    Node node = list.getFirst();
    while (node != null) {
        values.add(node.getData());
        node = node.getNext();
    }

    int[] arr = new int[values.size()];
    for (int index = 0; index < arr.length; ++index) {
        arr[index] = values.get(index);
    }
    return arr;
}

Here's a test case I'd like to work but it doesn't:

@Test
public void test_empty_reversed_is_empty() {
    assertArrayEquals(new int[]{}, reversed());
}

This fails, because SinglyLinkedList cannot be created empty. That's a pity, as an empty linked list is an interesting corner case, and I think it should be supported.

\$\endgroup\$
  • \$\begingroup\$ Thank you. But I'd use a variable size in SinglyLinkedList. It would let me to implement toArray without the extra ArrayList you use \$\endgroup\$ – Maksim Dmitriev Jul 14 '15 at 8:53
  • \$\begingroup\$ Sounds like a good idea! \$\endgroup\$ – janos Jul 14 '15 at 8:54
  • \$\begingroup\$ Node node = head; Is head mFirst? If so, your implementation is wrong. I initialize a list with int[] data = new int[] { 1, 2, 3, 4 }; linkedList.reversePairs2(); gives [1, 3, 2, 4] \$\endgroup\$ – Maksim Dmitriev Jul 14 '15 at 19:45
  • 1
    \$\begingroup\$ I renamed head to the more accurate sentinel, but forgot it in one place. Corrected now. Added a test case for 1, 2, 3, 4, the implementation correctly gives me 2, 1, 4, 3 \$\endgroup\$ – janos Jul 14 '15 at 19:54
  • 1
    \$\begingroup\$ If you have a specific requirement that you need to access the last element often, then yes, keeping track of it is a useful optimization. If you don't have such requirement, then this doesn't belong in a general-purpose linked list. \$\endgroup\$ – janos Jul 17 '15 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.