题目链接160. 相交链表 - 力扣LeetCode题目截图我的题解/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ // 长度差对齐法 // 1. 分别遍历两个链表求出链表 A、链表 B 的长度 // 2. 让长链表的指针先走「两链表长度差」步 // 3. 之后两个指针同步一步一步往后移动 // 4. 当两个指针**内存地址相等**就是相交起始节点遍历完都不等返回 NULL。 class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // p1遍历链表Ap2遍历链表B ListNode *p1headA,*p2headB; // len1保存链表A长度len2保存链表B长度 int len10,len20; // 统计两个链表的节点个数 while(p1!NULL){ len1; p1p1-next; } while(p2!NULL){ len2; p2p2-next; } // 指针重置回各自链表头结点准备对齐起点我一开始忘了 p1headA,p2headB; // 保证p1永远指向更长的那条链表len1是长链表长度len2短链表长度 if(len2len1){ // 函数std :: swap是C 标准模板库STL中的内置函数 // 不返回任何内容它交换两个变量的值。 // 参数可以是任何数据类型swapab swap(p1,p2); swap(len1,len2); } // 计算两条链表的长度差 int chalen1-len2; // 长链表指针p1先走【长度差】步使得剩余未遍历的链表长度相等 while(cha--){ p1p1-next; len1--; } // 此时p1、p2后面剩余节点数相同同步向后走找第一个相同地址的节点 // 相交链表判断的是节点地址相等不是val值相等 while(len1--){ // 如果指针指向同一个节点找到相交起点直接返回 if(p1p2){ return p1; } len2--; p1p1-next; p2p2-next; } // 循环结束没有找到相同节点说明链表不相交返回NULL return NULL; } };
