Java joining lists depending on values,

this code snippet performs in one iteration so order is O(N). pleas try to run with your dataset and let me know if any issues.

public class Test {
public static void main(String[] args) {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    List<Integer> one = new ArrayList<Integer>();one.add(1);one.add(2);
    List<Integer> two = new ArrayList<Integer>();two.add(2);two.add(3);
    List<Integer> three = new ArrayList<Integer>();three.add(3);three.add(1);
    List<Integer> four = new ArrayList<Integer>();four.add(4);four.add(7);
    List<Integer> five = new ArrayList<Integer>();five.add(7);five.add(4);
    List<Integer> six = new ArrayList<Integer>();six.add(6);six.add(2);
    list.add(one);list.add(two);list.add(three);list.add(four);list.add(five);list.add(six);

    System.out.println(list);

    List<List<Integer>> output = new ArrayList<List<Integer>>();

    for(int i=0;i<list.size();i++)
    {
        List<Integer> current = list.get(i);
        List<Integer> last = output.size() == 0 ? null : output.get(output.size()-1);
        if(null != last)
        {
            if(current.get(0)==last.get(last.size()-1))
            {
                last.addAll(current.subList(1, current.size()));
                output.set(output.size()-1, last);
            }
            else
            {
                output.add(current);
            }
        }
        else
        {
            output.add(current);
        }
    }

    System.out.println(output);
}
}

This seems to do what you are looking for - at least it generates the output you stated for the test input. I hope I have interpreted your needs correctly.

I have not stopped the ring at last == first as that does not match your expected output. I have stopped the ring when it touches an already visited entry. See your example - your entry [6,2] would never reach back to 6 and so would never stop.

// Finds which entry in the list is the target of the specified entry.
private int findTarget(List<List<Integer>> list, int pos) {
    // Look for that value.
    int targetValue = list.get(pos).get(1);
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i).get(0) == targetValue) {
            return i;
        }
    }
    return -1;
}

private List<List<Integer>> findAllRings(List<List<Integer>> list) {
    // Maintain a BitSet to keep track of all visited nodes.
    BitSet visited = new BitSet(list.size());
    // The rings.
    List<List<Integer>> rings = new ArrayList<>();
    // Carry on until all entries have been visited.
    int start = 0;
    while (start < list.size()) {
        // Where we are in the list.
        int pos = start;
        // Grow a new ring.
        List<Integer> ring = new ArrayList<>();
        // Stop when we touch one we have already seen.
        boolean ringClosed;
        do {
            // The value to add.
            ring.add(list.get(pos).get(0));
            // Stop if it already was set.
            ringClosed = visited.get(pos);
            // Track it's visited.
            visited.set(pos);
            if (!ringClosed) {
                // Move pos.
                pos = findTarget(list, pos);
                if (pos < 0) {
                    // No next pair - break this ring.
                    ringClosed = true;
                }
            }
        } while (!ringClosed);
        // One ring!
        rings.add(ring);

        // All done - move i forward until we find an unvisited node.
        while (start < list.size() && visited.get(start)) {
            start += 1;
        }
    }
    return rings;
}

public void test() {
    List<List<Integer>> startList = new ArrayList<>(Arrays.asList(
            Arrays.asList(new Integer[]{1, 2}),
            Arrays.asList(new Integer[]{2, 3}),
            Arrays.asList(new Integer[]{3, 1}),
            Arrays.asList(new Integer[]{4, 7}),
            Arrays.asList(new Integer[]{7, 4}),
            Arrays.asList(new Integer[]{6, 2}),
            Arrays.asList(new Integer[]{6, 3}),
            Arrays.asList(new Integer[]{9, 9})
    ));
    List<List<Integer>> resultList = findAllRings(startList);
    for (List<Integer> result : resultList) {
        System.out.println(result);
    }
}

Prints:

[1, 2, 3, 1]
[4, 7, 4]
[6, 2]
[6, 3]
[9, 9]

as requested.

Edit: Used a Map to remove the need for the inner loop. We should now be approximately O(n). Edit: Changed usage of BitSet to record the offset of the pair, not the value in the first entry of the pair - stops the BitSet blowing up for real int values. Removed the Map as it is no longer an optimisation.