Leetcode#160Intersection 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.

  • 문제 분석에 의하면 이 문제를 보면hash 함수를 사용하여 두 체인표를 처리하는 것을 직접 생각하면 시간 복잡도 o(n) 공간 복잡도 o(n)이다.
    그러나 제목은 시간 복잡도 o(n) 공간 복잡도 o(1)를 요구하기 때문에hash를 사용하여 이 문제를 처리할 수 없습니다.우리는 두 개의 체인 시계가 교차한다고 생각한다. 즉, 뒷부분은 중합되고 두 개의 체인 시계는 길고 짧으며 중합 부분은 반드시 가장 짧은 체인 시계 안에 존재한다.따라서 가장 짧은 체인 시계의 길이로 긴 체인 시계의 앞부분을 잘라낸 다음에 짧은 체인 시계와 순서대로 체인 시계의 노드를 비교하여 중합이 있는지 확인한다.
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            int La=0;
            int Lb=0;
            ListNode a=headA;
            while(a!=null)
            {
                La++;
                a=a.next;
            }
            ListNode b=headB;
            while(b!=null)
            {
                Lb++;
                b=b.next;
            }
            if(La==Lb)
            {
                a=headA;
                b=headB;
                while(a!=null)
                {
                    if(a==b)
                        return a;
                    a=a.next;
                    b=b.next;
                }
            }
            else if(La>Lb)
            {
                a=headA;
                b=headB;
                int i=0;
                while(i            {
                    i++;
                    a=a.next;
                }
            }
            else
            {
                a=headA;
                b=headB;
                int i=0;
                while(i            {
                    i++;
                    b=b.next;
                }
            }
            
            while(a!=null)
            {
                if(a==b)
                    return a;
                a=a.next;
                b=b.next;
            }
            return null;
                
        }
    }

    좋은 웹페이지 즐겨찾기