本文共 692 字,大约阅读时间需要 2 分钟。
输入两个链表,找出它们的第一个公共结点。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
由于单链表中节点只能有一个next指针,所以两个单链表相交,只能是Y型的形状,两者的尾部重叠,第一个重叠的节点就是我们要找的第一个公共节点。
假设链表1的长度为a + c,链表2的长度为b + c,c是两者的共同部分的长度。现在将两个链表按照不同顺序拼接,得到两个长度相同的新链表:a+c+b+c、b+c+a+c,然后从头依次遍历,则两个新链表第一次相同的节点就是第一个共同节点。
/*public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; }}*/public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode l1 = pHead1, l2 = pHead2; while (l1 != l2) { l1 = (l1 == null) ? pHead2 : l1.next; l2 = (l2 == null) ? pHead1 : l2.next; } return l1; } }
转载地址:http://sfnii.baihongyu.com/