java剑指offer:两个链表的第一个公共结点
描述
输入两个无环的单链表,找出它们的第一个公共结点。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
解题思路:
先假设链表A头结点与结点8的长度 与 链表B头结点与结点8的长度相等,那么就可以用双指针。
- 初始化:指针ta指向链表A头结点,指针tb指向链表B头结点
- 如果ta == tb, 说明找到了第一个公服务器托管网共的头结点,直接返回即可,否则,ta != tb,则++ta,++tb
所以现在的问题就变成,如何让本来长度不相等的变为相等的?
假设链表A长度为a, 链表B的长度为b,此时a != b
但是,a+b == b+a
因此,可以让a+b作为链表A的新长度,b+a作为链表B的新长度。
拼接两个链表的长度往下走会找到长链表与短链表的长度差。
- 双指针法。创建两个指针p1和p2,分别指向两个链表的头结点,然后依次往后遍历。如果某个指针到达末尾,则将该指针指向另一个链表的头结点;如果两个指针所指的节点相同,则循环结束,返回当前指针指向的节点。
- 短链表的指针p1会先到达尾部,然后重新指向长链表头部,当长链表的指针p2到达尾部时,重新指向短链表头部,此时p1在长链表中已经多走了k步(k为两个链表的长度差值),p1和p2位于同一起跑线,往后遍历找到相同节点即可。
- 其实该方法主要就是用链表循环的方式替代了长链表指针先走k步这一步骤。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFir服务器托管网stCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2==null)
return null;
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while(p1!=p2){
p1 = p1==null ? pHead2 : p1.next;
p2 = p2==null ? pHead1 : p2.next;
}
return p1;
}
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
项目介绍 日志脱敏是常见的安全需求。普通的基于工具类方法的方式,对代码的入侵性太强,编写起来又特别麻烦。 sensitive 提供了基于注解的方式,并且内置了常见的脱敏方式,便于开发。 日志脱敏 为了金融交易的安全性,国家强制规定对于以下信息是要日志脱敏的: …