/* Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting

node. Note that the intersection is defined based on reference, not value. That is, if the kth

node of the first linked list is the exact same node (by reference) as the jth node of the second

linked list, then they are intersecting. */

​

using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        Check check = new Check();

        // Not intersecting

        int[] numbers = new int[]{1,2,3,4};

        Node listOne = LinkedList.CreateLinkedList(numbers);

        Node listTwo = LinkedList.CreateLinkedList(numbers);

        Console.WriteLine("Given two lists has no intersection. Expected Answer is False. Program answer is " + check.TheyIntersect(listOne, listTwo));

        Console.WriteLine(" Using Dictionary - Given two lists has no intersection. Expected Answer is False. Program answer is " + check.TheyIntersect_UsingDictionary(listOne, listTwo));

        // Intersecting

        Node node1 = new Node(1,null);

        Node node2 = new Node(2,node1);

        Node listOneFirst = new Node(3,node2);

        Node node4 = new Node(4,node1);

        Node listTwoFirst = new Node(5,node4);

        Console.WriteLine("Given two lists do intersect. Expected Answer is True. Program answer is " + check.TheyIntersect(listOneFirst, listTwoFirst));

        Console.WriteLine("Using Dictionary - Given two lists do intersect. Expected Answer is True. Program answer is " + check.TheyIntersect_UsingDictionary(listOneFirst, listTwoFirst));

    }

}

​

public class Check

{

    public bool TheyIntersect(Node node1, Node node2)

    {

        Node listTwoFirst = node2;

        while(node1 != null)

        {

            while(node2 != null)

            {

                if(Object.ReferenceEquals(node1, node2))

                    return true;

                node2 = node2.Next;

            }

            node1 = node1.Next;

            node2 = listTwoFirst;

        }

        return false;

    }

    public bool TheyIntersect_UsingDictionary(Node node1, Node node2)

    {

        Dictionary<Node,int> nodeDictionary = new Dictionary<Node,int>();  

        while(node1 != null)

        {

            nodeDictionary.Add(node1,1);

            node1 = node1.Next;

        }

        while(node2 != null)

        {

            if(nodeDictionary.ContainsKey(node2))

                return true;

            node2 = node2.Next;

        }

        return false;

    }

}

​

public static class LinkedList

{

    public static int Length(Node first)

    {

        int count = 0;

        if(first == null)

            return 0;

        Node node = first;

        while(node != null)

        {

            count++;

            node = node.Next;

        }

        return count;

    }

    public static Node PadZerosOnHead(Node first, int numberOfZeros)

    {

        Node node = first;

        for(int i = 1; i<= numberOfZeros; i++)

        {

            node = AddToHead(node,0);           

        }

        return node;

    }

    public static Node CreateLinkedList(int[] numbers)

    {

        Node first = new Node(numbers[0], null);

        for(int i = 1; i<numbers.Length; i++)

        {

            Node node = first; 

            for(int j = i - 1; j > 0 ; j--)

            {

                node = node.Next; 

            }

            Node newNode = new Node(numbers[i],null); 

            node.Next = newNode;

        }

        return first;

    }

    public static Node RemoveNode(Node first, int data)

    {

        Node node = first;

        if(node.Data == data)

        {

            return node.Next;

        }

        while(node.Next != null) 

        {

            if(node.Next.Data == data)

            {

                node.Next = node.Next.Next;

                return first;

            }

            node = node.Next;

        }

        return first;

    }

    public static Node AddToTail(Node first, int data)

    {

        if(first == null)

        {

            return new Node(data,null);  

        }

        Node node = first;

        while(node.Next != null)

        {

            node = node.Next;

        }

        Node newNode = new Node(data,null); 

        node.Next = newNode;

        return first;

    }

    public static Node AddToHead(Node first, int data)

    {

        if(first == null)

        {

            return new Node(data,null); 

        }

        Node newNode = new Node(data,null); 

        newNode.Next = first;

        return newNode;

    }

    public static void DisplayLinkedList(Node first)

    {

        Node node = first;

        String a = first.Data.ToString() + " => ";

        while(node.Next != null)

        {

            node = node.Next;

            a += node.Data.ToString() + " => "; 

        }

        a = a.Remove(a.Length - 4, 4);

        Console.WriteLine(a);

    }

}

​

public class Node

{

    public int Data;

    public Node Next;

    public Node(int data, Node next)

    {

        this.Data = data;

        this.Next = next;

    }

}