本文共 1208 字,大约阅读时间需要 4 分钟。
题目:输入两个链表,找出它们的第一个公共结点。
思路:详见剑指offer. 理解什么是公共结点,所谓公共结点是指这个结点是两个链表共有的,不是指具有相同值得两个结点。由于链表是单链表,因此,两个链表一旦有公共结点,那么之后的链表一定是公共的,即他们必然是尾部对其的Y字形。因此,在尾部对齐的情况下,开头可以不是对齐的,于是长链表经过几次移动直到与短链表对齐,之后开始一起移动遍历,并使用==比较两个结点对象是否相同,如果相同,直接返回即可。由于这里对于链表只需要进行遍历不需要进行返回,因此直接对头结点pHead1,pHead2进行遍历即可,不需要保留头结点。
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*///输入两个链表,找到他们的第一个公共结点,如果有公共结点,一定是Y字形结构,尾部对其。public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { //特殊的,如果有链表为null,就返回null if(pHead1==null||pHead2==null) return null; //先计算出两个链表的长度 int length1=this.listLength(pHead1); int length2=this.listLength(pHead2); //定义两个变量,表示长链表和段链表 ListNode headLong=null; ListNode headShort=null; //得到两个链表的长度差,作为距离 int lengthDiff=0; if(length1>length2){ lengthDiff=length1-length2; headLong=pHead1; headShort=pHead2; }else{ lengthDiff=length2-length1; headLong=pHead2; headShort=pHead1; } //调整步长差,然后一起遍历 for(int i=0;i
转载地址:http://zvzin.baihongyu.com/