교차 링크 (데이터 구조 기초 회고)

하나의 프로그램 을 만들어 서 두 개의 단일 체인 표 가 교차 하 는 시작 노드 를 찾 습 니 다.
아래 의 두 개의 링크 와 같다.
노드 c1 에서 교차 하기 시작 합 니 다.
 
예시 1:
입력: intersectVal = 8, lista = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3 출력: Reference of the node with value = 8 입력 해석: 교차 노드 의 값 은 8 (주의, 두 링크 가 교차 하면 0 이 될 수 없습니다).각자 의 시계 머리 부터 계산 하면 링크 A 는 [4, 1, 8, 4, 5] 이 고 링크 B 는 [5, 0, 1, 8, 4, 5] 이다.A 에서 교차 노드 앞 에 2 개의 노드 가 있다.B 에서 교차 노드 앞 에 세 개의 노드 가 있다.
 
예시 2:
입력: intersectVal = 2, lista = [0, 9, 1, 2, 4], listB = [3, 2, 4], skipA = 3, skipB = 1 출력: Reference of the node with value = 2 입력 해석: 교차 노드 의 값 은 2 (주의, 두 링크 가 교차 하면 0 이 될 수 없습니다).각자 의 시계 머리 부터 계산 하면 링크 A 는 [0, 9, 1, 2, 4] 이 고 링크 B 는 [3, 2, 4] 이다.A 에서 교차 노드 앞 에 3 개의 노드 가 있다.B 에서 교차 노드 앞 에 1 개의 노드 가 있다.
 
예시 3:
입력: intersectVal = 0, lista = [2, 6, 4], listB = [1, 5], skipA = 3, skipB = 2 출력: null 입력 해석: 각자 의 표 머리 부터 계산 하면 링크 A 는 [2, 6, 4] 이 고 링크 B 는 [1, 5] 이다.이 두 개의 링크 가 교차 하지 않 기 때문에 intersectVal 은 0 이 어야 하고 skipA 와 skipB 는 임 의 값 일 수 있 습 니 다.설명: 이 두 체인 시 계 는 교차 하지 않 기 때문에 null 로 돌아 갑 니 다.
 
주의:
    만약 두 개의 체인 시계 가 교점 이 없다 면, null 로 돌아 갑 니 다.    결 과 를 되 돌려 준 후에 도 두 개의 링크 는 원래 의 구 조 를 유지 해 야 한다.    전체 링크 구조 에 순환 이 없다 고 가정 할 수 있다.    프로그램 은 O (n) 시간의 복잡 도 를 최대한 만족 시 키 고 O (1) 메모리 만 사용 합 니 다.링크:https://leetcode-cn.com/problems/intersection-of-two-linked-lists
이 문제 에서 제 생각 은 링크 의 길이 와 비교적 긴 링크 로 두 개의 링크 의 차 이 를 이동 시 켜 두 개의 링크 의 길이 가 같 고 길이 가 같다 는 것 입 니 다. 두 개의 지침 을 각각 두 개의 링크 를 옮 겨 다 니 면 교차 여부 와 교차 하 는 첫 번 째 노드 를 얻 을 수 있 습 니 다. 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==nullptr||headB==nullptr)
        {
            return NULL;
        }
        int a=0;
        int b=0;
        ListNode *p=headA;
        ListNode *q=headB;
        while(headA!=nullptr)
        {
            a++;
            headA=headA->next;
        }
        while(headB!=nullptr)
        {
            b++;
            headB=headB->next;
        }
        if(a>b)
        {
            while(a-b>0)
            {
                p=p->next;
                a--;
            }
        }
        else
        {
            while(b-a>0)
            {
                q=q->next;
                b--;
            }
        }
        while(p!=nullptr)
        {
            if(p==q)
            {
                return p;
            }
            p=p->next;
            q=q->next;
        }
        return nullptr;
    }
};