江苏龙网

  1. 首页 > 人文 > >

462. 找出两个链表的第一个公共节点( 二 )


462. 找出两个链表的第一个公共节点文章插图
最后再来看下代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//统计链表A和链表B的长度int lenA = length(headA), lenB = length(headB);//如果节点长度不一样 ， 节点多的先走 ， 直到他们的长度一样为止while (lenA != lenB) {if (lenA > lenB) {//如果链表A长 ， 那么链表A先走headA = headA.next;lenA--;} else {//如果链表B长 ， 那么链表B先走headB = headB.next;lenB--;}}//然后开始比较 ， 如果他俩不相等就一直往下走while (headA != headB) {headA = headA.next;headB = headB.next;}//走到最后 ， 最终会有两种可能 ， 一种是headA为空 ，//也就是说他们俩不相交 。 还有一种可能就是headA//不为空 ， 也就是说headA就是他们的交点return headA;}//统计链表的长度private int length(ListNode node) {int length = 0;while (node != null) {node = node.next;length++;}return length;}双指针解决
我们还可以使用两个指针 ， 最开始的时候一个指向链表A ， 一个指向链表B ， 然后他们每次都要往后移动一位 ， 顺便查看节点是否相等 。 如果链表A和链表B不相交 ， 基本上没啥可说的 ， 我们这里假设链表A和链表B相交 。 那么就会有两种情况 ，
一种是链表A的长度和链表B的长度相等 ， 他们每次都走一步 ， 最终在相交点肯定会相遇 。
一种是链表A的长度和链表B的长度不相等 ， 如下图所示
462. 找出两个链表的第一个公共节点文章插图
虽然他们有交点 ， 但他们的长度不一样 ， 所以他们完美的错开了 ， 即使把链表都走完了也找不到相交点 。
我们仔细看下上面的图 ， 如果A指针把链表A走完了 ， 然后再从链表B开始走到相遇点就相当于把这两个链表的所有节点都走了一遍 ， 同理如果B指针把链表B走完了 ， 然后再从链表A开始一直走到相遇点也相当于把这两个链表的所有节点都走完了
所以如果A指针走到链表末尾 ， 下一步就让他从链表B开始 。 同理如果B指针走到链表末尾 ， 下一步就让他从链表A开始 。 只要这两个链表相交最终肯定会在相交点相遇 ， 如果不相交 ， 最终他们都会同时走到两个链表的末尾 ， 我们来画个图看一下
462. 找出两个链表的第一个公共节点文章插图
462. 找出两个链表的第一个公共节点文章插图
如上图所示 ， A指针和B指针如果一直走下去 ， 那么他们最终会在相交点相遇 ， 最后再来看下代码
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//tempA和tempB我们可以认为是A,B两个指针ListNode tempA = headA;ListNode tempB = headB;while (tempA != tempB) {//如果指针tempA不为空 ， tempA就往后移一步 。//如果指针tempA为空 ， 就让指针tempA指向headB（注意这里是headB不是tempB）tempA = tempA == null ? headB : tempA.next;//指针tempB同上tempB = tempB == null ? headA : tempB.next;}//tempA要么是空 ， 要么是两链表的交点return tempA;}注意：这里所说的指针并不是C语言中的指针 ， 在这里其实他就是一个变量 ， 千万不要搞混了 。
问题分析
第一种解法应该是都容易想到的 ， 但效率不高 ， 一个个存储 ， 然后再拿另一个链表的节点一个个判断 。 最后一种解法没有统计链表的长度 ， 而是当一个链表访问完如果没有找到相交点 ， 就从下一个链表继续访问 ， 一般不太容易想到 ， 也算是比较经典的 。


推荐阅读


上一篇：6大细节盘点，总有一个你不知道！荣耀猎人游戏本评测

下一篇：有没有听过《真还传》？