Check whether LinkedList is an SubList

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

I need to write function public int subList (CharList list) that gets list and returns how many times this list exist. For example if my list is a b c d a b g e and the list received as parameter is a b it will return 2. The method should be as efficient as possible.

Currently my problem is that I don't know how to loop over the two lists at the same time in order to compare the values

Answer 1

To loop over the two lists at the same time:

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
}

For the complete solution, you will have to loop over your list once, and the other list as many times as there are matches. Let's take your example, a b c d a b g e compared to 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)