[Linked List][Easy] 160. Intersection of Two Linked Lists

https://leetcode.com/problems/intersection-of-two-linked-lists/description

 

Q. 두개의 노드가 도중에 교차할 때 해당 교차지점을 찾아서 반환하라. 

 

 Solution

    방법을 알면 간단한 문제다. 

    시작 지점을 align 시키는 것이 키인데, 보통의 풀이법은 두 리스트를 하나씩 전진시켜, 끝에 도달하면 반대 쪽 head에서 다시 출발한다. 이때 재출발 후, 두 노드가 만나는 지점이 교차점이 된다. 

    두 노드의 오프셋이 다르므로 이를 다른 노드의 시작점으로 재출발 시키면서 오프셋을 동기화 시킨 것이다. 

 

 

public ListNode GetIntersectionNode(ListNode headA, ListNode headB) 
{
    ListNode nodeA = headA;
    ListNode nodeB = headB;

    bool doneA = false, doneB = false;
    while(true)
    {
        if(nodeA == null)
        {
            if(!doneA)
                nodeA = headB;
            else 
                return null;
            doneA = true;
        }

        if(nodeB == null)
        {
            if(!doneB)
                nodeB = headA;
            else 
                return null;
            doneB = true;
        }

        if(nodeA == nodeB)
            return nodeA;

        nodeA = nodeA.next;
        nodeB = nodeB.next;
    }
    return null;
}

 

 

적절한 결과를 얻었다.