首页 > 代码库 > 【LeetCode】Intersection of Two Linked Lists
【LeetCode】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.
可以将A,B两个链表看做两部分，交叉前与交叉后。
交叉后的长度是一样的，因此交叉前的长度差即为总长度差。
只要去除这些长度差，距离交叉点就等距了。
为了节省计算，在计算链表长度的时候，顺便比较一下两个链表的尾节点是否一样，
若不一样，则不可能相交，直接可以返回NULL
/** * 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 == NULL || headB == NULL) return NULL; int lenA = 1; ListNode* curA = headA; while(curA->next != NULL) { lenA ++; curA = curA->next; } //now curA is the tail of A int lenB = 1; ListNode* curB = headB; while(curB->next != NULL) { lenB ++; curB = curB->next; } //now curB is the tail of B if(curA != curB) //no intersection return NULL; else { //align int diff = lenA-lenB; if(diff > 0) {//A go while(diff) { headA = headA->next; diff--; } } else {//B go while(diff) { headB = headB->next; diff++; } } //go together while(true) {//A and B has judged to intersect, no need to avoid NULL if(headA == headB) return headA; else { headA = headA->next; headB = headB->next; } } } }};
【LeetCode】Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。