两个链表的第一个公共节点

题目描述

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

注意：
如果两个链表没有交点，返回null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
公共节点

来源：LeetCode

解法一

用hashset可以很快解决问题，即先把链表1的所有节点指针放入set，遍历链表2时，如果找到有相等的指针，则说明这就是第一个公共节点，遍历结束还没找找到，说明没有相交节点。但这种方法的空间复杂度是O(n)，如何找到O(1)的方法呢？这里O(1)必然是使用双指针，分别遍历两个链表，但因为两个链表长度的问题，一次遍历肯定不行，第二次遍历如何继续？
因为相交必须是严格的数学推导出的，我们把节点a1…a2的长度记为a，把b1…b3的长度记为b，把公共c1…c3的长度记为c，要判断是否相交，则通过a+c+b=b+c+a这个等式判断，即在链表1第一次遍历结束后，马上从链表2的开始位置继续遍历，链表2同理。在遍历的过程中比较指针是否相等。如果两个链表没有相交，第二次遍历时，会同时指向最后的null，返回null即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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) {
        ListNode * p1 = headA;
        ListNode * p2 = headB;
        while(p1 != p2) {
            p1 = p1 != NULL ? p1->next : headB;
            p2 = p2 != NULL ? p2->next : headA;
        }
        return p1;
    }
};