wordpress二次元主页,吉林做网站优化,百度电话销售,医院招聘网站建设和维护人员目录
1.题目
代码模板
2.分析
编辑 算法误区
正确方法1
但不能通过所有的测试用例
修改后
提交结果
正确方法2
节省代码的技巧 1.题目
https://leetcode.cn/problems/3u1WK4/description/ 给定两个单链表的头节点 headA 和 headB #xff0c;请找出并返回两个单…目录
1.题目
代码模板
2.分析
编辑 算法误区
正确方法1
但不能通过所有的测试用例
修改后
提交结果
正确方法2
节省代码的技巧 1.题目
https://leetcode.cn/problems/3u1WK4/description/ 给定两个单链表的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 注意函数返回结果后链表必须 保持其原始结构 。 示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,0,1,8,4,5], skipA 2, skipB 3
输出Intersected at 8
解释相交节点的值为 8 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [4,1,8,4,5]链表 B 为 [5,0,1,8,4,5]。
在 A 中相交节点前有 2 个节点在 B 中相交节点前有 3 个节点。示例 2 输入intersectVal 2, listA [0,9,1,2,4], listB [3,2,4], skipA 3, skipB 1
输出Intersected at 2
解释相交节点的值为 2 注意如果两个链表相交则不能为 0。
从各自的表头开始算起链表 A 为 [0,9,1,2,4]链表 B 为 [3,2,4]。
在 A 中相交节点前有 3 个节点在 B 中相交节点前有 1 个节点。示例 3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2
输出null
解释从各自的表头开始算起链表 A 为 [2,6,4]链表 B 为 [1,5]。
由于这两个链表不相交所以 intersectVal 必须为 0而 skipA 和 skipB 可以是任意值。
这两个链表不相交因此返回 null 。提示 listA 中节点数目为 mlistB 中节点数目为 n0 m, n 3 * 1041 Node.val 1050 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA 1] listB[skipB 1] 进阶能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案 注意本题与主站 160 题相同160. 相交链表 - 力扣LeetCode 代码模板
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
}
2.分析
旧版分析见L10.【LeetCode笔记】环形链表(判断链表中是否有环)(旧版)文章
读题可知,对于两个链表相交可能有以下三种情况 中间节点相交 头结点相交(下图为A链表的中间节点和B链表的头节点相交) 尾节点相交 但绝对不存在“X”形的相交情况,一个节点只能有一个next指针 算法误区
设两个指针p1和p2分别从A和B链表的头节点出发,不能通过p1-valp2-val来判断到达了相交节点,会对不相交的链表造成误判 正确方法1
将A链表的每个节点的地址和B链表的所有节点的地址进行比较,如果相等则可求出相交节点的地址
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode * pAheadA;struct ListNode * pBheadB;while(pA!pB){if (pBNULL){pBheadB;pApA-next;}if (pANULL)return NULL;pBpB-next;}return pA;
}
但不能通过所有的测试用例 原因:pB-nextNULL,因此pBpB-next为pBNULL-next,不合法,尾部相交会出问题 修改后 其实只需要交换下判断的顺序即可
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode * pAheadA;struct ListNode * pBheadB;while(pA!pB){if (pANULL)return NULL;pBpB-next;if (pBNULL){pBheadB;pApA-next;}}return pA;
} 提交结果 这种方法时间复杂度为,不推荐使用
正确方法2
双指针算法时间复杂度为,参见L7.【LeetCode笔记】相交链表(旧版)
其实双指针的代码还可以写的更简洁些
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode * tailAheadA;struct ListNode * tailBheadB;int lenA1;int lenB1;//求A和B链表的长度while (tailA-next){tailAtailA-next;lenA;}while (tailB-next){tailBtailB-next;lenB;}//两个while循环结束后,tailA和tailB分别指向各自链表的尾部节点if (tailA!tailB)return NULL;//非尾部相交,返回NULL//头部相交和中间相交的情况int distanceabs(lenA-lenB);//假设A链表为长链表,B链表为短链表struct ListNode * longlistheadA;struct ListNode * shortlistheadB;//假设不成立再更正,节省代码if (lenAlenB){longlistheadB;shortlistheadA;} while (distance--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}
节省代码的技巧
假设A链表为长链表(longlis接收),B链表为短链表(shortlist接收),如果假设不成立,再更正(修改longlist和shortlist),这样就不用做if{...}else{...}了,减少重复代码
