.leetcode(160. Intersection of Two Linked Lists)

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

 

2. 2022/05/01 시도

소요시간: 7분

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        
        // check size
        int sizeA = 0;
        ListNode current = headA;
        while(current != null) {
            sizeA++;
            current = current.next;
        }
        
        int sizeB = 0;
        current = headB;
        while(current != null) {
            sizeB++;
            current = current.next;
        }
        
        // set same size 
        if (sizeA > sizeB) {
            for (int i=0; i<sizeA-sizeB; i++) {
                headA = headA.next;
            }
        } else {
            for (int i=0; i<sizeB-sizeA; i++) {
                headB = headB.next;
            }
        }
            
        // compare node
        while (headA != null) {
            if (headA == headB) {
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        
        return null;
    }
}

풀이 접근 과정

둘 중에 하나라도 null이면 같을 수가 없으니 null로 리턴해준다.

각각의 링크드리스트의 길이를 잰다.
똑같이 길이를 맞춘 후 비교할 수 있도록 긴길이를 짧게 맞춰준다.

같은 길이가 되면 하나씩 비교해보면서 전진한다.
같은 노드가 있으면 리턴하고 없으면 null이 리턴된다.

 

느낀점

• 길이라는 특성을 생각해보면 쉽게 풀릴 수 있는 문제다.
• 지난 풀이에서는 맨뒤로 돌아가서 하나씩 다시 비교하는 로직을 생각했는데 조금 발전했다.

 

---

1. 2022/01/10 시도

소요시간: 20분

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        LinkedList<ListNode> aStack = new LinkedList<>();       
        while(headA != null) {
            aStack.push(headA);
            headA = headA.next;
        }

        LinkedList<ListNode> bStack = new LinkedList<>();
        while(headB != null) {
            bStack.push(headB);
            headB = headB.next;
        }

        ListNode prev = null;
        ListNode al = aStack.pop();
        ListNode bl = bStack.pop();
        while(al != null && bl != null && al == bl) {
            prev = al;
            if (aStack.size() == 0 || bStack.size() == 0) {
                break;
            }
            al = aStack.pop();
            bl = bStack.pop();
        }

        return prev;
    }
}

풀이 접근 과정

맨 뒤까지가다가 달라지는 지점을 찾아서 리턴하면 되겠다.

 

느낀점

• 풀긴풀었는데 뭔가 깔금하지 못한 느낌이 들었다.
• 솔루션3번에서는 둘의 길이차이가 문제라는 힌트를 줘서 길이차이를 빼서 다시 계산하는 로직을 짜보았다. 잘 돈다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형