java - 检查LinkedList是否是子列表

Question

public class CharNode {
    private char _data;
    private CharNode _next;
    public CharNode(char dat, CharNode n) {
        _data = dat;
        _next = n;
    }
    public char getData() {
       return _data;
    }
    public CharNode getNext() {
        return _next;
    }
    public void setData(char d) {
       _data = d;
    }
    public void setNext(CharNode node) {
       _next = node;
     }
}

public class CharList {
    private CharNode _head;
    public CharList( ) {
        _head = null;
    }
    public CharList (CharNode node) {
        _head = node;
    }

    public int subList(IntList list)
    {
        int count = 0;
        IntNode listNode = _head;
        IntNode otherListNode = list._head; ;

        while (listNode != null)
        {
            if (otherListNode == null)
                otherListNode = list._head;
            if (listNode.getValue() == otherListNode.getValue())
            {
                listNode = listNode.getNext();
                otherListNode = otherListNode.getNext();
                if (otherListNode == null)
                    count++;
            }
            else
            {
                listNode = listNode.getNext();
                otherListNode = list._head;
            }              
        }

        return count;
    }
}

我需要编写函数public int subList (CharList list)来获取list并返回该列表存在的次数。例如，如果我的列表是 a b c d a b g e 并且作为参数接收的列表是 a b 它将返回 2。方法应该尽可能高效。

目前我的问题是我不知道如何同时循环两个列表以比较值

Answer 1

同时循环两个列表:

public bool equalsSubList(CharNode other) {
  CharNode node1 = this;  
  CharNode node2 = other;  
  while (node1 != null && node2 != null) { 
    // compare data from both nodes
    node1 = node1.getNext();
    node2 = node2.getNext();
  }
  // return true if all nodes where compared and are equal
}

对于完整的解决方案，您必须循环遍历您的列表一次，并循环遍历另一个列表，次数与匹配项相同。让我们举个例子，a b c d a b g e 与 a b 进行比较:

other |   this
      |
a b   |   a b c d a b g e 
^     |   ^ (match a, go to next in both lists)
a b   |   a b c d a b g e   |
  ^   |     ^ (match a b, counter is 1, go to next this, restart other)
a b   |   a b c d a b g e
^     |       ^ (does not match a, go to next this, restart other)
a b   |   a b c d a b g e
^     |         ^ (does not match a, go to next this, restart other)
a b   |   a b c d a b g e
^     |           ^ (match a, go to next in both lists)
a b   |   a b c d a b g e
  ^   |             ^ (match a b, counter is 2, go to next this, restart other)
a b   |   a b c d a b g e
^     |               ^ (does not match a, go to next this, restart other)
a b   |   a b c d a b g e
^     |                 ^ (does not match a, go to next this, restart other)