深圳网站做的好的公司名称,傻瓜式php网站开发工具,建工网校一建,贵州网站建设seo优化目录
题目要求
手搓两个相交简易链表
代码实现 题目要求
两个单链表的头节点 headA 和 headB #xff0c;请找出并返回两个单链表相交的起始节点#xff0c;如果两个链表不存在相交节点#xff0c;则返回 NULL 手搓两个相交简易链表
代码演示#xff1a;
struct Lis…目录
题目要求
手搓两个相交简易链表
代码实现 题目要求
两个单链表的头节点 headA 和 headB 请找出并返回两个单链表相交的起始节点如果两个链表不存在相交节点则返回 NULL 手搓两个相交简易链表
代码演示
struct ListNode* a1 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(a1);
struct ListNode* a2 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(a2);a1-val 1;
a2-val 2;a1-next a2;struct ListNode* b1 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(b1);
struct ListNode* b2 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(b2);
struct ListNode* b3 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(b3);b1-val 1;
b2-val 2;
b3-val 3;b1-next b2;
b2-next b3;struct ListNode* c1 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(c1);
struct ListNode* c2 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(c2);
struct ListNode* c3 (struct ListNode*)malloc(sizeof(struct ListNode));
assert(c3);c1-val 1;
c2-val 2;
c3-val 3;a2-next c1;
b3-next c1;
c1-next c2;
c2-next c3;
c3-next NULL; 代码实现
代码演示
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{// 先找各自链表的尾节点判断是否相交struct ListNode* tailA headA;struct ListNode* tailB headB;int lenA 1;int lenB 1;while (tailA-next ! NULL){tailA tailA-next;lenA;}while (tailB-next ! NULL){tailB tailB-next;lenB;}if (tailA ! tailB)return NULL;// 找相交节点int gap abs(lenA - lenB);struct ListNode* longList headA;struct ListNode* shortList headB;if (lenA lenB){longList headB;shortList headA;}while (gap--){longList longList-next;}while (longList ! shortList){longList longList-next;shortList shortList-next;}return longList;
}
代码解析
代码思路先判断两个链表是否相交那么就是看尾节点是否相同不相同就说明不相交返回NULL 即可尾节点相同则表示相交再将节点长的链表走差距步然后再同时往后走找到相同的节点时就是相交的节点
代码逻辑两个链表各自往后走并记录各自节点的个数先判断尾节点的地址是否相同注意不是判断两个节点的数据是否相同不想同就返回 NULL 相同就利用 abs 函数求出 lenA 减去 lenB 的绝对值就是两个链表相差的节点个数再求出长的链表先走差距步再一起往后走走到地址相同的节点时就时交点
代码验证
算法的时间和空间复杂度
3 个 while 循环执行了 N 次也就是 3*N除去 3 且没有产生额外的空间
时间复杂度 O(N)
空间复杂度O(1)
