C++LeetCode 실현(160.두 개의 링크 의 교점 구하 기)

[LeetCode]160.Intersection of Two Linked Lists 는 두 개의 링크 의 교점 을 구한다.
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A:          a1 → a2
K
c1 → c2 → c3
J           
B:     b1 → b2 → b3
begin to intersect at node c1.
Notes:
  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.
  • Credits:
    Special thanks to  @stellari  for adding this problem and creating all test cases.
    나 는 앞으로 OJ 문 제 를 공짜 로 풀 수 없 을 줄 알 았 는데,OJ 가 책 을 사지 않 고도 풀 수 있 는 문 제 를 내 놓 을 줄 은 몰 랐 다.업계 양심 이 야,하하^ ^.이 두 개의 링크 를 구 하 는 교점 문 제 는 집행 시간 이 O(n)이 어야 하 며,유사 한 거품 법 원 리 를 이용 하여 같은 점 을 폭력 적 으로 찾 을 수 없다.사실은 링크 가 길 면 그러한 방법 은 효율 이 매우 낮 다 는 것 을 증명 한다.나 도 이전에 중복 요 소 를 삭제 한 문제 처럼 두 개의 지침 으로 옮 겨 다 녀 야 하 는 것 이 아 닐 까 생각 했 지만 오랫동안 생각 했 지만 어떻게 해 야 할 지 생각 나 지 않 았 다.어 쩔 수 없 이 인터넷 에서 신 들 의 해법 을 찾 아 보 니 해법 은 간단 하 다.두 체인 의 길이 가 같다 면 대응 하 는 것 을 하나씩 비교 해 보면 찾 을 수 있 기 때문에 긴 링크 를 짧게 만 들 면 된다.구체 적 인 알고리즘 은 두 개의 링크 를 옮 겨 다 니 며 각각 대응 하 는 길 이 를 얻 는 것 이다.그 다음 에 길이 의 차 이 를 구하 고 비교적 긴 체인 시 계 를 뒤로 이동 시 킨 다음 에 이 차 이 를 일일이 비교 하면 된다.코드 는 다음 과 같 습 니 다: 
    C++해법 1:
    
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if (!headA || !headB) return NULL;
            int lenA = getLength(headA), lenB = getLength(headB);
            if (lenA < lenB) {
                for (int i = 0; i < lenB - lenA; ++i) headB = headB->next;
            } else {
                for (int i = 0; i < lenA - lenB; ++i) headA = headA->next;
            }
            while (headA && headB && headA != headB) {
                headA = headA->next;
                headB = headB->next;
            }
            return (headA && headB) ? headA : NULL;
        }
        int getLength(ListNode* head) {
            int cnt = 0;
            while (head) {
                ++cnt;
                head = head->next;
            }
            return cnt;
        }
    };
    자바 해법 1:
    
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            int lenA = getLength(headA), lenB = getLength(headB);
            if (lenA > lenB) {
                for (int i = 0; i < lenA - lenB; ++i) headA = headA.next;
            } else {
                for (int i = 0; i < lenB - lenA; ++i) headB = headB.next;
            }
            while (headA != null && headB != null && headA != headB) {
                headA = headA.next;
                headB = headB.next;
            }
            return (headA != null && headB != null) ? headA : null;
        }
        public int getLength(ListNode head) {
            int cnt = 0;
            while (head != null) {
                ++cnt;
                head = head.next;
            }
            return cnt;
        }
    }
    이 문 제 는 아주 교묘 한 방법 도 있다.비록 문제 에서 링크 에 고리 가 존재 하지 않 는 다 는 것 을 강 조 했 지만 우 리 는 링 의 사상 으로 할 수 있다.우 리 는 두 개의 링크 를 각자 의 시작 부터 뒤로 옮 겨 다 니 게 한다.그 중 하 나 는 끝까지 옮 겨 다 닐 때 우 리 는 다른 링크 의 시작 으로 계속 옮 겨 다 닐 수 있다.두 지침 은 결국 같 을 것 이 고 두 가지 상황 만 있 을 것 이다.하 나 는 교점 에서 만 나 는 것 이 고 다른 하 나 는 각자 의 끝의 빈 노드 에서 같다.왜 꼭 같 을 까?두 바늘 이 걸 어 가 는 길이 가 같 고 두 개의 링크 의 길이 의 합 이기 때문에 반드시 같 을 것 이다.이 사고방식 은 정말 교묘 하 다.그리고 더욱 중요 한 것 은 코드 를 아주 간결 하 게 쓰 는 것 이다.코드 는 다음 과 같다.
    C++해법 2:
    
    class Solution {
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
            if (!headA || !headB) return NULL;
            ListNode *a = headA, *b = headB;
            while (a != b) {
                a = a ? a->next : headB;
                b = b ? b->next : headA;
            }
            return a;
        }
    };
    자바 해법 2:
    
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode a = headA, b = headB;
            while (a != b) {
                a = (a != null) ? a.next : headB;
                b = (b != null) ? b.next : headA;
            }
            return a;
        }
    }
    유사 한 제목:
    Minimum Index Sum of Two Lists
    참고 자료:
    https://leetcode.com/problems/intersection-of-two-linked-lists/
    https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49792/Concise-JAVA-solution-O(1)-memory-O(n)-time
    https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!
    여기 서 C++실현 LeetCode(160.두 개의 링크 의 교점 을 구 합 니 다)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++실현 두 개의 링크 의 교점 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!

    좋은 웹페이지 즐겨찾기