java给定两个链表，找到其中一个链表是另一个链表的子链表的索引

Question

最近，我在大学里参加了一个java编码挑战，有人问我这个问题，我发现这个问题很难实现

问题是实现一个方法detect，该方法给定两个LinkedList，返回索引，其中第二个列表是第一个列表的子列表

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

列表的节点结构为

LinkedListNode {
   String val;
   LinkedListNode *next;
}

以及方法签名

static int detect(LinkedListNode list, LinkedListNode sublist)

解决这个问题的基本算法是什么。我是数据结构的新手

Answer 1

其基本思想是遍历第二个列表，并为此列表中的每个索引检查第一个列表中连续元素的相等性。以下算法适用于您：

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));
            }
        }
    }

这会按预期打印Index is: 1

Answer 2

因为，这里的值是字符串：-

static int find(LinkedListNode list, LinkedListNode sublist) {
    String listString = convertLinkedListToString(list);
    String sublistString = convertLinkedListToString(sublist);
    return listString.indexOf(sublistString);
}

private static String convertLinkedListToString(LinkedListNode list) {
    String listAsString = "";
    while(list != null) {
        listAsString = listAsString + list.val;
        list = list.next;
    }
    return listAsString;
}

Answer 3

static int detect(LinkedListNode list, LinkedListNode sublist) {
        int counter = 0;
        int index = -1;
        LinkedListNode sub = sublist;

        do {
            if (list.val == sub.val) {
                if (index == -1)
                    index = counter;
                if (sub.next != null) {
                    sub = sub.next;
                    if (sub.next == null) {
                        return index;
                    }
                }
            } else {
                index = -1;
                sub = sublist;
            }
            list = list.next;
            counter++;

        } while (list.next != null);

        return index;
    }