上海做网站优化公司头条今日头条新闻头条

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

思路一：模拟题意

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {if(!headA||!headB)return NULL;struct ListNode *p = headA,*q = headB;while(q!=p){q = q ? q->next:headA;p = p ? p->next:headB;}return p;}

分析：

本题返回相交链表的相交节点，可以利用pq两个指针记录遍历位置，当q==p时即遍历到相交节点，返回即可

总结：

本题考察对链表的利用，利用指针记录位置当两个指针到相交节点返回即可解决