首页 > 代码库 > Intersection of Two Linked Lists
Intersection of Two Linked Lists
题目描述:
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.
思路分析:先求出两段链表的长度length_a、length_b,让较长链表的头指针先移动|length_a-length_b|个单位。然后让两个链表的头指针一起移动,当两个指向两个链表的指针相等时,即找到了交点。
代码:
ListNode * Solution::getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode * a = headA; ListNode * b = headB; int length_a = 0,length_b = 0; while(a != NULL) { length_a++; a = a->next; } while(b != NULL) { length_b++; b = b->next; } if(length_a > length_b) { int difference = length_a - length_b; while(difference > 0) { difference--; headA = headA->next; } } else if(length_b > length_a) { int difference = length_b - length_a; while(difference > 0) { difference--; headB = headB->next; } } while(headA != headB) { headA = headA->next; headB = headB->next; } return headA; }
Intersection of Two Linked Lists
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。