算法:两个链表的第一个公共结点
两个链表的第一个公共结点
两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。
（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
分析
设定两个指针分别从list1和list2开始.
list1当到达链表1结尾时, 继续从链表2开始; list2同理;
最后:
长度相同时
- 有公共结点，第一次就遍历到；
- 没有公共结点，走到尾部NULL相遇，返回NULL
长度不同时
- 有公共结点，第一遍差值就出来了，第二遍一起到公共结点
- 没有公共，一起到结尾NULL
代码
1
2
3
4
5
6
7
8
9
10
| public class Solution {
public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
ListNode list1 = head1, list2 = head2;
while (list1 != list2) {
list1 = list1 == null ? head2 : list1.next;
list2 = list2 == null ? head1 : list2.next;
}
return list1;
}
}
|
