首页 > 代码库 > 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.
Credits:
Special thanks to @stellari for adding this problem and creating all test cases.
Hide Tags
Linked List/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { int lenA=0,lenB=0; ListNode *tempA=headA; ListNode *tempB=headB; while(tempA){ lenA++; tempA=tempA->next; } while(tempB){ lenB++; tempB=tempB->next; } while(lenA>lenB){ headA=headA->next; lenA--; } while(lenB>lenA){ headB=headB->next; lenB--; } while(headA != headB){ headA=headA->next; headB=headB->next; } return headA; }};
Intersection of Two Linked Lists两链表找重合节点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。