《剑指offer》刷题系列——（十五）两个链表的第一个公共节点

题目

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

思路

第一种思路： 当两个链表出现交点时，交点出现在两个链表的尾部，所以如果能从两个链表尾部开始比较，那么最后一个相同的节点就是要找的节点。但是单向链表无法从尾部开始遍历，因此我们可以利用 栈 “后进先出”的特点，将两个链表分别遍历并将节点值存入两个栈中。接下来比较两个栈顶的节点是否相同，如果相同就弹出，并比较下一个，直到找到最后一个相同的节点。 当两个链表的长度分别为m和n时，这种方法的时间复杂度为O(m+n)，由于用到了两个辅助栈，所以空间复杂度也是O(m+n)。

第二种思路： 由于两个链表的长度不相同，但是尾部总有一段相交的部分，所以可以先分别遍历两个链表，记录他们的长度，然后让长链表先走完它多出的几步，然后再和短链表一起边走边比较。 这种方法的时间复杂度还是O(m+n)，但是空间复杂度也是O(1)。

第三种思路： 在题解里看到大神们的双指针相遇法，太强了。 假设两个链表的长度分别为A+C和B+C，C为相交的部分。 定义两个指针，两个指针同时开始遍历。 第一个指针的路线是先走完链表listA，然后开始走listB； 同时，第二个指针的路线是先走完链表listB，然后开始走listA； 两个指针什么时候会相遇呢？就是在它们的第一个交点处，因为此时它们同时都走了A+B+C的长度 时间复杂度O(m+n)，空间复杂度O(1)。

代码

思路二解法:

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: m,n=0,0 pa,pb = headA,headB while pa != None: m += 1 pa = pa.next while pb != None: n += 1 pb = pb.next if m==0 or n==0: return None if m >= n: num = m-n while num != 0: headA = headA.next num-=1 else: num = n-m while num != 0: headB = headB.next num-=1 while headA: if headA==headB: return headA headA=headA.next headB=headB.next return headA

思路三解法:

class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode: node1,node2 = headA,headB while node1!=node2: node1 = node1.next if node1 else headB node2 = node2.next if node2 else headA return node1