首页 > 代码库 > [LeetCode] Intersection of Two Linked Lists
[LeetCode] 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.
老题目了，复习一下。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution {10 public:11 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {12 ListNode *pA, *pB;13 int lenA, lenB;14 pA = headA; 15 lenA = 0;16 while (pA != NULL) {17 ++lenA;18 pA = pA->next;19 }20 pB = headB; 21 lenB = 0;22 while (pB != NULL) {23 ++lenB;24 pB = pB->next;25 }26 int idx = lenA > lenB ? (lenA - lenB) : (lenB - lenA);27 pA = headA; pB = headB;28 if (lenA > lenB) {29 while (idx--) {30 pA = pA->next;31 }32 } else {33 while (idx--) {34 pB = pB->next;35 }36 }37 while (pA != pB) {38 pA = pA->next;39 pB = pB->next;40 }41 return pA;42 }43 };
[LeetCode] Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。