Given two Linked Lists, find the index where one list is sublist of another

Question

Recently I took part in a java coding challenge in my college and was asked this problem which I found difficult to implement.

Problem was to implement a method detect that given two LinkedList, return the index where second list is sublist of first.

detect((1,2,3),(2,3)) should return 1

The node structure to the list was

LinkedListNode {
   String val;
   LinkedListNode *next;
}

and the method signature

static int detect(LinkedListNode list, LinkedListNode sublist)

What would be the basic algorithm to approach this problem. I am a newbie to data structures.

Answer 1

I believe Collections.indexOfSubList implements this. You can look at it's implementation. Basically:

    ListIterator<?> si = source.listIterator();
    nextCand:
        for (int candidate = 0; candidate <= maxCandidate; candidate++) {
            ListIterator<?> ti = target.listIterator();
            for (int i=0; i<targetSize; i++) {
                if (!eq(ti.next(), si.next())) {
                    // Back up source iterator to next candidate
                    for (int j=0; j<i; j++)
                        si.previous();
                    continue nextCand;
                }
            }
            return candidate;
        }

Answer 2

The basic idea is to traverse the second list and for every index in this list check for equality in first list for consecutive elements. The following algorithm will work for you:

public static void main(String[] args) {
        List<Integer> list1 = new LinkedList<Integer>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        list1.add(4);
        list1.add(5);
        list1.add(6);
        List<Integer> list2 = new LinkedList<Integer>();
        list2.add(2);
        list2.add(3);


        boolean contains = true;
        int currIndex = 0;
        int i = 0,j = 0;
        for(;j<list2.size();j++) {
            int e2 = list2.get(j);
            for(i=currIndex;i<list1.size();i++) {
                if(e2 == list1.get(i)) {
                    break;
                }
            }
            if(i == list1.size()) {
                contains = false;
                break;
            }
            currIndex++;
            if( contains && (currIndex == list2.size()) ) {
                System.out.println("Index is: " + (i-j));
            }
        }
    }

This prints Index is: 1 as expected.