分析:两个单链表如果存在第一个公共结点,则后续结点一定都公共,
因为结点里包含next指针,如果第一个公共结点相同,则next必然相同,
所以第一个公共结点后链表合并。
思路1:设表1长度n,表2长度m,暴力法嵌套遍历两个链表需要O(mn)的时间复杂度,
可以采用hash的思想将其中一个转存为哈希表结构,这样建哈希表时间O(m),
而遍历链表时间O(n),而遍历时查找哈希表的时间为O(1),因此复杂度降为O(m+n),
但需要辅助空间。(这种哈希优化的策略是种一般性的思路,谨记!)
思路2:无需记录链表长度(巧妙,难度大,想不到)
假设p1比较短,p1长度s1, 第一个结点位置为1
p1换到链表2头时:p2链表2的走到了s1+1的位置
p2换到链表1头时:p1在链表2走到了1(起始位置)+[s2-(s1+1)](p1交换后p2剩余还要走的长度)+1(走到NULL的长度,这时才算换到P1头)
所以此时p1的位置为1+s2-s1,很明显了- - p1在链表2已经走了他们的长度差,而p2在链表1的头,他们之间相当于在同一起跑线,所以再走就能相遇了。
思路3:(常规思路)找出2个链表的长度,然后让长的先走两个链表的长度差,然后再一起走
(因为2个链表用公共的尾部
思路三