首页 > 代码库 > LeetCode Intersection of Two Linked Lists 解题报告
LeetCode Intersection of Two Linked Lists 解题报告
https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
求两个链表的第一个公共节点，如果不存在公共节点的话就返回null。
解题思路：
1）如果两个链表的最后一个节点一样，那么说明两个链表一定有交点。
2）分别求出两个链表的长度，然后对长度长的链表向前移动：LengA - LengB，将两个链表进行对齐，之后一起遍历，直到找到第一个相同的节点。
求两个链表的第一个公共节点，如果不存在公共节点的话就返回null。
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3解题思路：
1）如果两个链表的最后一个节点一样，那么说明两个链表一定有交点。
2）分别求出两个链表的长度，然后对长度长的链表向前移动：LengA - LengB，将两个链表进行对齐，之后一起遍历，直到找到第一个相同的节点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null||headB==null) {
return null;
}
int lengthA = 1;
int lengthB = 1;
ListNode iterA = headA;
while(iterA.next!=null) {
iterA = iterA.next;
lengthA++;
}
ListNode iterB = headB;
while(iterB.next!=null) {
iterB = iterB.next;
lengthB++;
}
if(iterA!=iterB) {
return null;
}
if(lengthA>lengthB) {
int tmp = lengthA - lengthB;
while(tmp>0) {
headA = headA.next;
tmp--;
}
} else {
int tmp = lengthB - lengthA;
while(tmp>0) {
headB = headB.next;
tmp--;
}
}
while(headA!=headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
}LeetCode Intersection of Two Linked Lists 解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。