[LeetCode] 160. Intersection of Two Linked Lists 解题思路

时间:2023-01-20 08:42:05

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2

c1 → c2 → c3

B: b1 → b2 → b3

begin to intersect at node c1.

Notes:

    • If the two linked lists have no intersection at all, return null.
    • The linked lists must retain their original structure after the function returns.
    • You may assume there are no cycles anywhere in the entire linked structure.
    • Your code should preferably run in O(n) time and use only O(1) memory.

问题:判断两个列表是否有相交的元素,若有,找出相交节点。

这题也是一道基础题,看了自己的列表知识还需要巩固下才好。

分别求出两个列表的长度 len1, len2 ,以及他们的长度差异 diff

跳过长度差异部分,对于剩余的相同长度部分,依次检查两个链表的对应节点,若又存在相交节点,则必有两个对应节点相等。

     ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

         int len1 = ;
ListNode* p1 = headA;
while(p1 != NULL){
p1 = p1->next;
len1++;
} int len2 = ;
ListNode* p2 = headB;
while(p2 != NULL){
p2 = p2->next;
len2++;
} p1 = headA;
p2 = headB;
if (len1 > len2){
int diff = len1 - len2;
while(diff > ){
p1 = p1->next;
diff--;
}
} if (len2 > len1){
int diff = len2 - len1;
while(diff > ){
p2 = p2->next;
diff--;
}
} while(p1 != NULL ){
if ( p1 == p2){
return p1;
}
p1 = p1->next;
p2 = p2->next;
} return NULL;
}

参考资料:

LeetCode: Intersection of Two Linked Lists 解题报告, Yu's garden