小游戏网站开发需要什么技术,昆明做网站的个人,wordpress外观主题制作,室内设计装修是什么专业题型#xff1a;链表基本操作
链接#xff1a;160. 相交链表 - 力扣#xff08;LeetCode#xff09;
来源#xff1a;LeetCode
题目描述
给你两个单链表的头节点 headA 和 headB #xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点链表基本操作
链接160. 相交链表 - 力扣LeetCode
来源LeetCode
题目描述
给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
题目样例
笔者这边为了方便理解省略了原本的大部分文字描述。有需求的可以看原文链接
示例 1 示例 2 示例 3 1 m, n 3 * 1041 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 *paheadA,*pbheadB;int lena0,lenb0;while(pa ! NULL){lena;papa-next;}while(pb ! NULL){lenb;pbpb-next;}// 保证A链表一定是长链表方便后续操作if(lenalenb){swap(lena,lenb);swap(headA,headB);}paheadA,pbheadB;for(int i0;ilena-lenb;i){papa-next;}while(pa !NULL pb!NULL){if(papb)return pa;pa pa-next;pb pb-next;}return NULL;}
};
结算页面
