题目描述
输入两个链表，找出它们的第一个公共结点。
题解
本题可以将两个链表的节点存放在两个栈中，这样两个链表的尾节点就位于栈顶，然后依次比较栈顶是否相同，得到最后一个相同的栈顶元素即为两个链表的第一个公共节点。但是这种方法需要两个辅助栈，时间复杂度和空间复杂度都是O(m+n)。
还有一个更简单的方法，可将空间复杂度降至O(1)。首先遍历两个链表，统计两个链表长度的差值。然后先在较长的链表上先走若干步，步数为这些差值。最后同时在两个链表上开始遍历，找到第一个公共节点。
public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null)
return null;
// 首先遍历两个链表，统计两个链表长度的差值。
ListNode p = head1, q = head2;
int count1 = 0, count2 = 0;
while (p != null) {
count1++;
p = p.next;
}
while (q != null) {
count2++;
q = q.next;
}
// 先在较长的链表上先走若干步，步数为这些差值。
if (count1 > count2) {
int diff = count1 - count2;
while (diff > 0) {
head1 = head1.next;
diff--;
}
} else {
int diff = count2 - count1;
while (diff > 0) {
head2 = head2.next;
diff--;
}
}
// 最后同时在两个链表上开始遍历，找到第一个公共节点。
while (head1 != head2) {
head1 = head1.next;
head2 = head2.next;
}
return head1;
}
