一.题目及剖析
https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
这道题无非就是要做两件事,一是判断链表是否相交,而是找到这个交点
二.思路引入
1.判断链表是否相交只需要判断尾节点地址是否相同(注意一定不能去判断value是否相同)
2.如果尾节点相同,则遍历链表拿到两个链表的长度
3.让长链表先走,走到剩余长度与短链表相同时两者一块走,直到找到一个节点的地址相同,返回该节点
三.代码引入
/** * 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* curA = headA; ListNode* curB = headB; int lenA = 0; while(curA->next) { curA = curA->next; lenA++; } int lenB = 0; while(curB->next) { curB = curB->next; lenB++; } if(curA != curB) return NULL; int gap = abs(lenA - lenB); ListNode* longList = headA; 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; }
