稀碎从零算法笔记Day19-LeetCode:相交链表

题型：链表基本操作

链接：160. 相交链表 - 力扣（LeetCode）

来源：LeetCode

题目描述

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

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

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

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

题目样例

笔者这边为了方便理解，省略了原本的大部分文字描述。有需求的可以看原文链接

示例 1：

示例 2：

示例 3：

1 <= m, n <= 3 * 104
1 <= Node.val <= 105

题目思路

因为样例图自动【右端对齐】了，于是脑子抽掉，居然想直接遍历两个链表，如果指针相同就可以直接rt；

虽然被样图 ”误导“，但提前【右端对齐】的思路可以实现：①遍历链表获得两个链表的长度（为了方便理解以及实现，可领 listA 为长链表，这样 lena 的长度自然要大于 lenb 了），让 listA 提前跑lena-lenb个距离，这样就实现了两个链表的右端对齐，进而可以使用上面的思路了

C++代码

/*** 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) {// 规定：链表A长度 > 链表B的长度ListNode *pa=headA,*pb=headB;int lena=0,lenb=0;while(pa != NULL){lena++;pa=pa->next;}while(pb != NULL){lenb++;pb=pb->next;}// 保证A链表一定是长链表，方便后续操作if(lena<lenb){swap(lena,lenb);swap(headA,headB);}pa=headA,pb=headB;for(int i=0;i<lena-lenb;i++){pa=pa->next;}while(pa !=NULL && pb!=NULL){if(pa==pb)return pa;pa = pa->next;pb = pb->next;}return NULL;}
};