leetcode

A collection of 1 post

Oct 4, 2015

相交链表 (找出两个链表的公共结点)

一图胜千言,看图你就明白了空间复杂度 O(1)O(1) 时间复杂度为 O(n)O(n)这里使用图解的方式,解释比较巧妙的一种实现。根据题目意思如果两个链表相交,那么相交点之后的长度是相同的我们需要做的事情是,让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。为此,我们必须消除两个链表的长度差指针 pA 指向 A 链表,指针 pB 指向 B 链表,依次往后遍历如果 pA 到了末尾,则 pA