• 周五. 7月 1st, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

剑指offer解题报告(Java版)——找到两个链表的第一个公共节点 37

admin

11月 28, 2021

   

引言

   

这个问题一种常想到的方法就是两层循环遍历,外层循环遍历链表A,对A中每个节点,遍历链表B,如果在B中找到,说明这个节点是第一个公共节点,但是这样的方法时间复杂为mn,一般是不允采用的

   

分析问题

   

所以我们需要分析更深层次的问题,找到其中的规律,我们如果动手画一下一般的链表图就能够发现两个链表的第一个公共节点之后的样子一定是如下表示(由此可以发现有时候动手是很重要的)

   

   

可以发现两个链表在第一个节点重合之后不会再分开了

   

简单多说一句不会分开的原因,因为单向链表的节点只有一个nextNode指向下一个节点,那么如果该节点重合了,那么后面的节点一定是同一个

   

如果直观点对这个图形进行解释就是两个链表重合之后呈现一个Y型而不是一个X

   

解决问题

   

一般这种问题要用两个类似指针的东西,一个先走,一个后走

   

所以我们先遍历找到两个链表的长度mn,如果m大,mn大多少,比如说k,那么先让m先走k步,然后nm再一起走

   

ListNode findFirstCommonNode(ListNode root1, ListNode root2) {

ListNode resultNode = null;

int length1 = getLength(root1);

int length2 = getLength(root2);

   

ListNode LongList;

ListNode ShortList;

int steps = 0;

if (length1 > length2) {

LongList = root1;

ShortList = root2;

steps = length1 – length2;

} else {

LongList = root2;

ShortList = root1;

steps = length2 – length1;

}

   

for (int i = 0; i < steps; i++) {

LongList = LongList.nextNode;

}

while (LongList != null && ShortList != null && LongList != ShortList) {

LongList = LongList.nextNode;

ShortList = ShortList.nextNode;

}

   

resultNode = LongList;

return resultNode;

   

}

   

测试代码

   

public static void main(String[] args) {

ListNode head1=new ListNode();

ListNode second1=new ListNode();

ListNode third1=new ListNode();

ListNode forth1=new ListNode();

ListNode fifth1=new ListNode();

ListNode head2=new ListNode();

ListNode second2=new ListNode();

ListNode third2=new ListNode();

ListNode forth2=new ListNode();

head1.nextNode=second1;        

second1.nextNode=third1;

third1.nextNode=forth1;

forth1.nextNode=fifth1;

head2.nextNode=second2;

second2.nextNode=forth1;

third2.nextNode=fifth1;

head1.data=1;

second1.data=2;

third1.data=3;

forth1.data=6;

fifth1.data=7;

head2.data=4;

second2.data=5;

third2.data=6;

forth2.data=7;

FindFirstCommonNode test=new FindFirstCommonNode();

System.out.println(test.findFirstCommonNode(head1, head2).data);

}

发表评论

您的电子邮箱地址不会被公开。