160. Intersection of Two Linked Lists

두 개의 연결 리스트가 주어졌을 때, 두 리스트가 교차하는 지점을 찾는 문제입니다. 
교차 지점이 없으면 null을 반환해야 합니다.

 

List A:  A1 → A2
                  ↘
                    C1 → C2 → C3
                   ↗
List B:B1 → B2 → B3

이 경우, 리스트 A와 리스트 B는 C1에서 교차하고, 이 지점이 교차 지점이 됩니다.

두 연결 리스트의 길이를 각각 계산합니다.
두 리스트의 길이 차이를 구하고, 길이가 더 긴 리스트의 포인터를 그 차이만큼 이동시킵니다.
이제 두 포인터를 동시에 이동시켜 교차 지점을 찾습니다.

 

 

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = GetLength(headA);
        int lenB = GetLength(headB);

        // 길이가 더 긴 리스트의 포인터를 차이만큼 이동
        while (lenA > lenB) {
            headA = headA.next;
            lenA--;
        }

        while (lenB > lenA) {
            headB = headB.next;
            lenB--;
        }

        // 두 포인터를 동시에 이동하며 교차 지점 찾기
        while (headA != null && headB != null) {
            if (headA == headB) {
                return headA; // 교차 지점을 찾으면 반환
            }
            headA = headA.next;
            headB = headB.next;
        }

        return null; // 교차 지점이 없는 경우
    }

    // 연결 리스트의 길이 계산
    private int GetLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }
}

위 코드는 두 연결 리스트의 길이를 계산하고, 길이 차이를 구하여 포인터를 이동시키고, 두 포인터를 동시에 이동시켜 교차 지점을 찾는 방식을 사용합니다