剑指Offer:两个链表的第一个公共节点

题目

输入两个链表,找出它们的第一个公共结点。

分析

经过分析我们可以发现,两个链表存在公共节点,那么自第一个公共节点开始往后的所有节点将全部相同。所以,我们可以将两个链表的节点分别放到两个栈中,接下来只需要比较两个栈中的节点是否相同,如果相同就弹出,知道找到最后一个相同的节点。

但是使用辅助栈就意味着要占用一部分内存,下面我们介绍一种不占内存且时间效率和第一种方法同为O(m+n)的方法。

第一种方法之所以需要栈,是因为我们相同时遍历两个链表的尾节点。当两个链表的长度不一样时,如果我们从头开始遍历,那么到达尾节点的时间就不一致。为了解决这个问题,我们可以先遍历两个链表得到他们的长度,我们就能知道那个链表更长,并且两个链表相错的长度。第二次遍历的时候我们想让较长的链表先走若干步(两个链表相错的长度),然后两个链表就可以同时访问了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int length1 = 0;
int length2 = 0;
ListNode node = pHead1;
while (node != null) {
++length1;
node = node.next;
}
node = pHead2;
while (node != null) {
++ length2;
node = node.next;
}
int difLength = length1 - length2;

ListNode pLongHead = pHead1;
ListNode pShortHead = pHead2;
if (length2 > length1) {
pLongHead = pHead2;
pShortHead = pHead1;
difLength = length2-length1;
}

for (int i = 1; i <= difLength; i ++)
pLongHead = pLongHead.next;
while (pLongHead != null && pShortHead!=null && pLongHead.val != pShortHead.val) {
pLongHead = pLongHead.next;
pShortHead = pShortHead.next;
}
ListNode pFirstCommonNode = pLongHead;
return pFirstCommonNode;
}
}