两个有公共节点链表的第一个公共节点（程序员的浪漫只有程序猿懂）

如题：我们有两种解决办法

第一种

分别计算两个链表长度，然后计算差值，设差值为x，另长的链表先跳x步，然后在另两个链表一块跳，跳到相等的节点停下，此时即为结果。

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int sizeA=0,sizeB=0; ListNode ahead=headA,bhead=headB; while(headA!=null){ headA=headA.next; sizeA++; } while(headB!=null){ headB=headB.next; sizeB++; } int cha=Math.abs(sizeB-sizeA); if(sizeA>sizeB){ for(int i=0;i<cha;i++){ ahead=ahead.next; } while(ahead!=bhead&&ahead!=null){ ahead=ahead.next; bhead=bhead.next; } return ahead; } else{ for(int i=0;i<cha;i++){ bhead=bhead.next; } while(bhead!=ahead&&bhead!=null){ ahead=ahead.next; bhead=bhead.next; } return bhead; } }
}

  

 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35

第二种 用一种浪漫的方法解决 a走完a的路，继续走b的，b同样同时走完b的路走a的，当两个人相遇的时候就是我们想要的节点

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode ahead=headA,bhead=headB; while(ahead!=bhead){ ahead=ahead!=null?ahead.next:headB; bhead=bhead!=null?bhead.next:headA; } return ahead; }
}

  

 

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

文章来源: blog.csdn.net，作者：秦枫-_-，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_41884662/article/details/115921281