2.7 교집합

문제 

단방향 연결리스트 두개가 주어졌을때 이 두리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라. 여기서 교집합이란 노드의 값이 아니라 노드의 주소가 완전히 같은 경우를 말한다. 즉, 첫번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소가 된다.

 

해법

교집합 예제

교집합의 유무를 판별하기 위해서는 

우선 각 리스트의 마지막노드가 같아야하고, 같은 길이의 출발점에서부터 순차적으로 탐색을 했을때 동시에 방문하는 노드가 같은 점이 잇어야한다.

1. 각 연결리스트를 순회하면서 길이와 마지막 노드를 구한다.

2. 길이가 긴쪽의 리스트에서 짧은쪽과의 차이만큼 시작포인터를 옮긴다.

3. 두 포인터가 같아질때까지 두 리스트를 함께 순회한다.

def length_lastpoint(l):
    if l is None : return (0,None)
    cnt =1
    while l.next is not None:
        cnt +=1
        l = l.next
    return (cnt, l)

def get_start(l, cnt):
    for _ in range(cnt):
        l = l.next
    return l

def Solution(l1, l2):
    len_l1 ,p_l1= length_lastpoint(l1)
    len_l2 ,p_l2= length_lastpoint(l2)
    if len_l1 != len_l2 or p_l1 != p_l2:
        return None
    p_l1 = l1 if len_p1 >len_p2 else get_start(l1,len_p1-len_p2)
    p_l2 = l2 if len_p2 >len_p2 else get_start(l1,len_p2-len_p1)
    while p_l1 is not None:
        if p_l1 is p_l2 :
            return p_l1
        p_l1 = p_l1.next
        p_l2 = p_l2.next
    return None