公司网站开发费计入,亚马逊网站风格,php 网站缓存,网站建设合同违约金细节题目如下#xff1a; 解题过程如下#xff1a; 相交链表只可以在中间任意位置/头/尾结点相交#xff0c;如下图#xff1a; 一个next指针只能指向一块地址#xff0c;所以不会出现这种情况#xff1a;
在返回相交链表的起始结点之前先要判断两个链表是否相交#xff0… 题目如下 解题过程如下 相交链表只可以在中间任意位置/头/尾结点相交如下图 一个next指针只能指向一块地址所以不会出现这种情况
在返回相交链表的起始结点之前先要判断两个链表是否相交分析下列两种方法是否可行 遍历两个链表判断结点地址是否相同。如果像示例1一样两个链表的长度不等代码运行结果就是两个链表不会相交这与事实恰恰相反。所以这个方法不可行 看两个链表的尾结点地址是否相同。参考相交链表的三种情况尾结点相同那么两个链表就一定相交。
那么怎么返回相交链表的起始结点呢
思路求两个链表的长度长链表先走长度差步长短链表遍历比较结点的地址是否相同。 完整代码如下 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {//求两个链表的长度ListNode* pa headA;ListNode* pb headB;int sizeA 0;int sizeB 0;while (pa){sizeA;pa pa-next;}while (pb){sizeB;pb pb-next;}//长链表先走长度差gap步int gap abs(sizeA - sizeB);ListNode* shortList headA;ListNode* longList headB;//假设B是长链表if (sizeA sizeB){shortList headB;longList headA;}while (gap--){longList longList-next;}//长短链表遍历结点的地址是否相同while (longList) //等同于shortList ! NULL{if (longList shortList)return longList;longList longList-next;shortList shortList-next;}return NULL;
}abs()函数用于求绝对值
