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
Post a Comment