2
\$\begingroup\$

Given three linked lists, say a, b and c, find one node from each list such that the sum of the values of the nodes is equal to a given number. For example, if the three linked lists are 12->6->29, 23->5->8 and 90->20->59, and the given number is 101, the output should be tripel “6 5 90″.

This question is attributed to geeksforgeeks.

Looking for code review, optimizations, best practices. Please ignore reviews which include improvements to class / variable names. They are named so for personal reasons and well aware they need to be better.

class NodeLL {
    NodeLL next;
    int item;

    NodeLL(int item) {
        this.item = item;
    }
}

class LList {
    private NodeLL first;
    private NodeLL last;

    public LList(List<Integer> list) {
        for (int i : list) {
            add(i);
        }
    }

    private void add(int i) {
        NodeLL node = new NodeLL(i);
        if (first == null) {
            first = last = node;
        } else {
            last.next = node;
            last = node;
        }
    }

    public void setFirst(NodeLL first) {
        this.first = first;
    }

    public NodeLL getFirst() {
        return first;
    }

    public void setLast(NodeLL last) {
        this.last = last;
    }

    public NodeLL getLast() {
        return last;
    }

    public List<Integer> toList() {
        final List<Integer> list = new ArrayList<>();
        for (NodeLL x = first; x != null; x = x.next) {
            list.add(x.item);
        }
        return list;
    }
}


public final class TripletLL {

    private TripletLL() { }

    // this util function can be utilized independently, not just to find triple LL, thus kept it public
    public static void sort(LList linkedList) {
        NodeLL first = sort (linkedList.getFirst(), linkedList.getLast());
        linkedList.setFirst(first);
    }

    // this util function can be utilized independently, not just to find triple LL, thus kept it public
    public static NodeLL midPoint(NodeLL node) {
        NodeLL fast = node.next;
        NodeLL slow = node;

        while (fast != null && fast.next != null) {
            fast = fast.next.next; 
            slow = slow.next;
        }

        return slow; 
    }


    private static NodeLL sort (NodeLL nodeStart, NodeLL nodeEnd) {
        if (nodeStart == nodeEnd) return nodeStart;

        NodeLL midpoint = midPoint (nodeStart);
        NodeLL tempMidpoint = midpoint.next;
        midpoint.next = null;

        NodeLL n1 = sort (nodeStart, midpoint);
        NodeLL n2 = sort (tempMidpoint, nodeEnd);

        return merge(n1, n2); 
    }


    private static NodeLL merge (NodeLL node1, NodeLL node2) {
        assert node1 != null && node2 != null; 

        NodeLL head = null; 
        NodeLL prev = null;
        NodeLL aux = null;

        while  (node1 != null && node2 != null)  {
           if (node1.item < node2.item) {
               aux = node1;
               node1 = node1.next;
           } else {
               aux = node2;
               node2= node2.next;
           }

           if (prev == null) {
               head = prev = aux;
           } else {
               prev.next = aux;
               prev = aux;
           }
        }

        prev.next = node1 == null ? node2 : node1;

        return head;
    }

    private static void reverse(LList ll) {
        NodeLL prev = null;
        NodeLL curr = ll.getFirst();
        NodeLL next = ll.getFirst();

        while (curr != null) {
            next = next.next;
            curr.next = prev;
            prev = curr;  
            curr = next;
        }
        ll.setFirst(prev);
    }

    /**
     * Linkedlist structure changes, original structure is not maintained.
     * 
     * @param ll1       the first linkedlist.
     * @param ll2       the second linkedlist
     * @param ll3       the third linkedlist
     * @param value     the value, which individual nodes from a linkedlist should sum upto.
     * @return          the 3 values/items each belonging to different linkedlist, which sum to the value.
     */
    public static List<Integer> returnThree(LList ll1, LList ll2, LList ll3, int value) {
        final List<Integer> list = new ArrayList<Integer>();
        NodeLL node1 = ll1.getFirst();       // node belonging to first linkedlist

        sort(ll2);
        sort(ll3);

        reverse(ll3);

        NodeLL node2First = ll2.getFirst();  
        NodeLL node3First = ll3.getFirst();  

        NodeLL node2 = node2First; // node belonging to second linkedlist
        NodeLL node3 = node3First; // node belonging to second linkedlist

        boolean found = false;

        while (node1 != null) {

            while (node2 != null && node3 != null) {
                int sum = node1.item + node2.item + node3.item;
                if (sum == value) { 
                    list.add(node1.item);
                    list.add(node2.item);
                    list.add(node3.item);

                    found = true;
                    break;
                } else {
                    if (sum < value) {
                        node2 = node2.next;
                    } else {
                        node3 = node3.next;
                    }
                }
            }

            if (found) {
                break;
            }

            // resetting nodes to first.
            node2 = node2First;
            node3 = node3First;

            node1 = node1.next;
        }

        return list;
    }
}



public class TripletLLTest {

    @Test
    public void test1() {
        LList ll1 = new LList(Arrays.asList(12, 6, 29));
        LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
        LList ll3 = new LList(Arrays.asList(90, 20, 59));
        assertEquals(Arrays.asList(6, 5, 90), TripletLL.returnThree(ll1, ll2, ll3, 101));
    }


    @Test
    public void test2() {
        LList ll1 = new LList(Arrays.asList(12, 6, 29));
        LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
        LList ll3 = new LList(Arrays.asList(90, 20, 59));
        assertEquals(Arrays.asList(12, 5, 90), TripletLL.returnThree(ll1, ll2, ll3, 107));
    }


    @Test
    public void test3() {
        LList ll1 = new LList(Arrays.asList(12, 6, 29));
        LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
        LList ll3 = new LList(Arrays.asList(90, 20, 59));
        assertEquals(Arrays.asList(6, 23, 20), TripletLL.returnThree(ll1, ll2, ll3, 49));
    }

    @Test
    public void test4() {
        LList ll1 = new LList(Arrays.asList(12, 6, 29));
        LList ll2 = new LList(Arrays.asList(23, 5, 8, 9, 10));
        LList ll3 = new LList(Arrays.asList(90, 20, 59));
        assertEquals(Collections.EMPTY_LIST, TripletLL.returnThree(ll1, ll2, ll3, 50));
    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ personal reasons. This looks to me like you either named them that way because you have got some "namespace conflicts", or because you don't care. If you know they should be better, why don't you make them better? \$\endgroup\$ – Vogel612 Aug 13 '14 at 9:24
2
\$\begingroup\$

Naming

Good variable, class and method names make it easier to review code, so I'm with Vogel612, why not make them better (although I think that in this case most of them are fine)?

Comments

  • setFirst and setLast should be commented on. As I understand them, they are just there so that you can use them inside you program, not the way mjolka understood them? And in that case, they should better be protected instead of public.
  • node belonging to first linkedlist and node belonging to second linkedlist are not a very helpful comments. What I would like to know in returnThree is why you sort ll2 and ll3 (why reverse?), but not ll1? A couple of words to what your algorithm does and how it does it would be a lot more helpful than your current comments.
  • The comment of returnThree should document that an empty list will be returned if no result is found

Bugs

  • reverse and sort do not update last. Fields like that really should always be up-to-date, or it should be commented on that they are not.

Break

In some cases, using break makes sense, but in your code, I'd rather do it this way:

while (!found && node1 != null)

Tests

  • Your test lists are all the same, so just create them in setUp
  • Test also with other lists (all lists have 1 element, ll3 has more elements than ll2, the last element of ll2/ll3 is needed as result, etc)

Readability and Performance

Some methods, especially merge take a while to understand as they are quite complex. If readability and maintainability are concerns, I would write it something like this:

private static NodeLL merge (NodeLL node1, NodeLL node2) {
    LList output = new LList();
    while (node1 != null && node2 != null) {
        if (node1.item < node2.item) {
            output.add(node1.item);
            node1 = node1.next;
        } else {
            output.add(node2.item);
            node2 = node2.next;
        }
    }
    output.getFirst().next = node1 == null ? node2 : node1;
    return output.getFirst();
}

If your main concern is performance, your approach seems a lot better (it doesn't create a bunch of new objects). However, when I timed it, my approach was about 3 times as fast.

\$\endgroup\$
1
\$\begingroup\$

There are bugs in setFirst, setLast, and reverse. Consider this code:

LList list = new LList(Arrays.asList(1));
list.setFirst(new NodeLL(2));
System.out.printf("%d%n", list.getLast().item);

The expected behaviour would be to print 2, but it actually prints 1.

The same goes for this:

LList list = new LList(Arrays.asList(1));
list.setLast(new NodeLL(2));
System.out.printf("%d%n", list.getFirst().item);

and this:

LList list = new LList(Arrays.asList(2, 1));
TripletLL.reverse(list);
System.out.printf("%d%n", list.getLast().item);
\$\endgroup\$

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.