前言
本系列主要讲解链表的经典题
注：划重点！！必考~
链表分割
- 题目描述：
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回null。
示例：
提示：
listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
解题思路：
- 对两个链表进行分别遍历算出长度差
- 同时如果两链表末尾结点地址不同，则表示没有两链表没有相交
- 对长链表指针先走长度差个结点，再两个指针同时遍历
- 当两个结点指针相遇时即为相交节点
参考代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //创建寻址指针 struct ListNode*cur1=headA,*cur2=headB; //计算各链表的长度 int len1=1,len2=1,gas; while(cur1->next) { len1++; cur1=cur1->next; } while(cur2->next) { len2++; cur2=cur2->next; } //各链表尾节点不相等则两链表不相交 if(cur1!=cur2) return false; //接下来则是必定有相交节点的情况 //判断长短并记录 struct ListNode*geater,*less; if(len1>=len2) { geater=headA; less=headB; gas=len1-len2; } else { geater=headB; less=headA; gas=len2-len1; } //长链表先走差距长度 while(gas--) { geater=geater->next; } //一同走，相等时则找到相交节点 while(geater!=less) { geater=geater->next; less=less->next; } return geater; }
结果：
每日k题无烦恼，点赞学习不得了~
