首页 > 代码库 > 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.
C++ 实现代码：
#include<iostream>#include<new>#include<cmath>using namespace std;//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=length(headA); int lenB=length(headB); int len=0; ListNode *p=headA; ListNode *q=headB; if(lenA>=lenB) { len=lenA-lenB; while(p&&q) { if(p&&len) { len--; p=p->next; continue; } if(p->val!=q->val) { p=p->next; q=q->next; continue; } break; } } else { len=lenB-lenA; while(p&&q) { if(q&&len) { len--; q=q->next; continue; } if(p->val!=q->val) { p=p->next; q=q->next; continue; } break; } } if(p&&q) return p; else return NULL; } int length(ListNode *head) { if(head==NULL) return 0; ListNode *p=head; int len=0; while(p) { len++; p=p->next; } return len; } void createList(ListNode *&head,int *arr,int n) { ListNode *p=NULL; int i=0; for(i=0; i<n; i++) { if(head==NULL) { head=new ListNode(arr[i]); if(head==NULL) return; } else { p=new ListNode(arr[i]); p->next=head; head=p; } } }};int main(){ Solution s; ListNode *L1=NULL; ListNode *L2=NULL; ListNode *L=NULL; int arr1[10]= {12,11,9,7,5,3,1,0}; int arr2[10]= {12,11,8,6,4,2}; s.createList(L1,arr1,8); s.createList(L2,arr2,6); L=s.getIntersectionNode(L1,L2); cout<<L->val<<endl;}
Intersection of Two Linked Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。