Linked list contains a second linked list in O(N)

Check if one linked list contains a second linked list in O(N)

Example:

Given:

Linked list 1: 100 -> 120 -> 159 -> 77

Linked list 2: 1 -> 200-> 500 -> 100 -> 120 -> 159 -> 77

Then: The lists converge at address 100

Test:

        [TestMethod]
public void TestLinkedListContainsLinkedlist()
{
bool contains = LinkedListContainsLinkedList.Check(new[] {100, 120, 159, 77},
new[] {1, 200, 500, 100, 120, 159, 77});
Assert.IsTrue(contains);

bool doesntContain = LinkedListContainsLinkedList.Check(new[] { 100, 120, 159, 77 },
new[] { 1, 200, 500, 120, 159, 77 });
Assert.IsFalse(doesntContain);
}



Solution:

    public class LinkedListContainsLinkedList
{
public static bool Check(int[] list1, int[] list2)
{
int[] biggerList;
int[] smallerList;

if (list1.Length > list2.Length)
{
biggerList = list1;
smallerList = list2;
}
else
{
biggerList = list2;
smallerList = list1;
}

int seachIndex = biggerList.Length - smallerList.Length;
for (int i = seachIndex; i < biggerList.Length; i++)
{
bool theSame = biggerList[i] == smallerList[i-seachIndex];
if (!theSame)
{
return false;
}
}

return true;
}
}

Comments