[Leet Code] Intersection of Two Linked Lists (Java)

문제는 다음과 같다.

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

• write a solution that runs in O(m + n) time and use only O(1) memory

값이 아니라 주소를 기준으로 판단해야 한다 즉, val값은 별로 중요하지 않고 같은 주소를 갖는 노드인지 판단해야 한다. 독특한 아이디어가 필요했다.

A + B 와 B + A를 하나씩 비교하면 길이가 같기 때문에 어느 노드에서 합쳐지는지 알 수 있다

물론 합쳐지지 않는 경우도 고려해야 한다. 비교를 했을 때 둘 다 null 값일 경우는 2가지의 경우의 수(1. 아직 A 와 B의 길이가 같은 경우, 2. A + B를 모두 확인한 경우)가 있지만 출력해야 하는 값은 똑같이 null이다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
 
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
       ListNode a = headA;
       ListNode b = headB;
       while (a != b && (a != null || b != null))
       {
           a = (a == null)? headB : a.next;
           b = (b == null)? headA : b.next;
       }
       return a;
    }
}```