[알고리즘 / 링크드 리스트] Intersection of Two Linked Lists

문제

https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1215/

예시1

 

예시2

예시3

예시4

다음과 같은 Linked List(LL,링크드 리스트)가 주어졌을때, 서로 부딪히는(위 그림의 노란 체크) 노드 찾기

 

아이디어

일단 같은 길이의 위치에 놓은 후 한칸씩 건너며 체크한다

위와 같은 두 LL이 주어진다고 한다면

긴쪽의 head를 짧은 쪽의 head 에 맞게 옮긴후

이후 한칸씩 움직이면 Intersect 노드를 찾을 수 있음

제약조건

overflow등을 걱정할만한 제약조건은 없어보임

챌린지

time complexity : O(m + n)

Space complexity : O(1)

 

뼈대코드

/**
 * 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) {
        
        
    }
}

내가 한 코드

/**
 * 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) {
        // base cases
        // if(headA == null || headB ==null){
        //     return null;
        // }
        // if(headA == headB){
        //     return headA;
        // }
        
        long ptPos = 0;
        ListNode currA = headA, currB = headB;
        boolean mOrN = true;
        while(currA != null && currB != null){
            if(currA == currB){
                return currA;
            }
            currA = currA.next;
            currB = currB.next;
        }
        
        if(currA == null && currB ==null){
            return null;
        }
        
        if(currA != null){
            while(currA != null){
                ptPos++;
                currA = currA.next;
            }
        }
        
        if(currB != null){
            mOrN = false;
            while(currB != null){
                ptPos++;
                currB = currB.next;
            }
        }
        
        
        System.out.println(ptPos);
        currA = headA;
        currB = headB;
        //m is bigger
        if(mOrN){
            while(ptPos>0){
                currA = currA.next;
                ptPos--;
            }
        }else{
             while(ptPos>0){
                currB = currB.next;
                ptPos--;
            } 
        }
        
        while(currA != null && currB != null){
            if(currA == currB){
                return currA;
            }
            currA = currA.next;
            currB = currB.next;
        }
        
        return null;
        
    }
}

정답코드

충격적으로 간단

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA;
        ListNode pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
        // Note: In the case lists do not intersect, the pointers for A and B
        // will still line up in the 2nd iteration, just that here won't be
        // a common node down the list and both will reach their respective ends
        // at the same time. So pA will be NULL in that case.
    }
}