160. Intersection of Two Linked Lists
Description Submission Solutions Add to List
- Total Accepted: 112057
- Total Submissions: 372496
- Difficulty: Easy
- Contributors: Admin
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.
/** * 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) { if(!headA || !headA) return NULL; ListNode* tmp = headA; int lenA = 0, lenB = 0; while(tmp){ tmp = tmp -> next; lenA++; } tmp = headB; while(tmp){ tmp = tmp -> next; lenB++; } if(lenA > lenB){ int len = lenA - lenB; while(len > 0){ headA = headA -> next; len--; } }else if(lenA < lenB) { int len = lenB - lenA; while(len > 0){ headB = headB -> next; len--; } } while(headA != headB && headA && headB){ headA = headA -> next; headB = headB -> next; } return headA && headB ? headA : NULL; } };