求两个链表第一个交叉的节点
两个链表的第一个公共结点_牛客网
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&rp=2&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tPage=2
求两个链表的第一个交叉节点
1、题目：输入两个链表，找出它们的第一个公共结点。
2、思路：因为如果有交叉，从交叉的第一个节点开始，后面都共用节点。（1）先求出两个链表的长度（2）让长度较长的链表先走len1-len2步，这样剩下的长度相等了（3）两个链表同时走，判断是否相等；相等则返回节点的地址；否则继续（3）
3、代码：
public class PublicNode {
public class ListNode {
int val;
ListNode next;
public ListNode(int val, ListNode node) {
this.val = val;
this.next = node;
}
}
public static void main(String[] args) {
// 新建链表2个
PublicNode pn = new PublicNode();
ListNode p1 = pn.new ListNode(8, null);
ListNode head1 = p1;
ListNode p2 = pn.new ListNode(9, null);
ListNode head2 = p2;
for (int i = 0; i < 5; i++) {
ListNode p = pn.new ListNode(i, null);
if (i < 2) {
p1.next = p;
p1 = p;
} else {
p1.next = p;
p1 = p;
p2.next = p;
p2 = p;
}
}
System.out.println(pn.FindFirstCommonNode(head1, head2).val);
}
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
// 求长度
int pLen1 = getLengh(pHead1);
int pLen2 = getLengh(pHead2);
// 让一个链表先走len1-len2步
if (pLen1 > pLen2) {
pHead1 = firstGo(pHead1, pLen1 - pLen2);
} else {
pHead2 = firstGo(pHead2, pLen2 - pLen1);
}
// 同时走，判断是否相等
while (pHead1 != null) {
if (pHead1 == pHead2) {
break;
} else {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
}
return pHead1;
}
// 得到长度
public int getLengh(ListNode node) {
int len = 0;
while (node != null) {
len++;
node = node.next;
}
return len;
}
// 一个链表先走len1-len2步
public ListNode firstGo(ListNode node, int len) {
while (len > 0) {
len--;
node = node.next;
}
return node;
}
}
投递银联等公司10个岗位 >
