链表的相交

链表的相交

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

给你两个单链表的头节点?headA?和?headB?，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回?null?。

思路：
让长的链表先走gap步，走完之后一起走，若有交点的话，return longList,无交点的话longList最后为NULL.

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *tailA=headA;
    struct ListNode *tailB=headB;
    int lenA=1,lenB=1;
    while(tailA){
        ++lenA;
        tailA=tailA->next;
    }
    while(tailB){
        lenB++;
        tailB=tailB->next;
    }
    int gap=abs(lenA-lenB);
    //长的先走差距步，在同时走找到交点
    struct ListNode *longList=headA;
    struct ListNode *shortList=headB;
    if(lenA<lenB){
        shortList=headA;
        longList=headB;
    }
    while(gap--){
        longList=longList->next;
    }
    while(longList!=shortList){
        longList=longList->next;
        shortList=shortList->next;
    }
    return longList;
}

测试链表的一段代码：
?

#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//Definition for singly - linked list.
struct ListNode {
    int val;
	struct ListNode* next;
};
int main() {
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;
	n2->val = 1;
	n3->val = 1;
	n4->val = 1;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;
	return 0;
}