男女做暧昧试看网站/优化营商环境工作总结

题目描述

输入两个链表，找出它们的第一个公共结点。

解题思路

由题意可知，两个链表后半部分出现重合，则我们可以分别定义两个指针指向各个链表的表头，从表头开始向后移动来查找重合的节点。这其中有一个问题，那就是如果两个链表长度不一致的情况，此时应先让长度较长的那个链表的指针先行移动，移动的距离为两个链表的长度之差，当较长的链表指针移动到等长位置后，两个指针再同时移动，每移动一次判断两个指针指向的节点是否一样，相同则返回指针，不同则继续移动，知道移动到链表尾部，如果还没有相同节点则返回空！

图示

代码实现

去博客设置页面，选择一款你喜欢的代码片高亮样式，下面展示同样高亮的 代码片.

class ListNode{ //定义链表节点ListNode next;int val;public ListNode(ListNode listNode,int val){this.val=val;this.next=listNode;}public ListNode(){}
}public class findFirstCommonNode {//寻找两个链表的第一个公共节点public ListNode findCommon(ListNode pHead1,ListNode pHead2){if (pHead1==null||pHead2==null){return null;}ListNode node1=pHead1;ListNode node2=pHead2;int listLength1=0;//定义链表长度int listLength2=0;while (node1!=null){//计算链表长度listLength1++;node1=node1.next;}while (node2!=null){listLength2++;node2=node2.next;}node1=pHead1;//定义一个指针指向头节点node2=pHead2;if(listLength1>listLength2){//当链表1长度大于链表2长度时，链表1指针后移至与链表2长度相等for (int i=0;i<listLength1-listLength2;i++){node1=node1.next;}}else if(listLength1<listLength2){//链表2长度大于链表1，链表2指针后移for (int i=0;i<listLength2-listLength1;i++){node2=node2.next;}}while (node1!=null&&node2!=null&&node1!=node2){//此时两个链表指针后的长度相等，寻找公共节点node1=node1.next;node2=node2.next;}return node1;}public static void main(String[] args) {ListNode node1 = new ListNode();ListNode node2 = new ListNode();ListNode node3 = new ListNode();ListNode node4 = new ListNode();ListNode node5 = new ListNode();ListNode node6 = new ListNode();ListNode node7 = new ListNode();ListNode node8 = new ListNode();node1.val = 1; node1.next = node2;node2.val = 3; node2.next = node3;node3.val = 5; node3.next = node7;node7.val = 11; node7.next = node8;node8.val = 15; node8.next = null;node4.val = 4; node4.next = node5;node5.val = 6; node5.next = node6;node6.val = 7; node6.next = node7;findFirstCommonNode test=new findFirstCommonNode();ListNode node = test.findCommon(node1,node4);System.out.println(node.val);}
}

总结

本题来源于面试经典教材《剑指offer》中 归属于链表类型题目。
同许多在算法道路上不断前行的人一样，不断练习，修炼自己！
如有博客中存在的疑问或者建议，可以在下方留言一起交流，感谢各位！
最后，感谢Jerry算法！