当前位置：首页 > news >正文

链表篇： 04-寻找两个链表的第一个公共结点

news 来源：原创 2024/9/19 9:48:44

解题思路：

方案一：长度统计法

从题目中可以看到，两个链表有长度差，这里可以先让长度比较长的链表先把长度差走完，这里假设为 pHead1, 先让 pHead1 把长度差走完，之后让两个链表同时往后进行遍历，最后当两个链表的值相等时，就直接返回

import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {// 方案一 长度统计法pHead1 = this.getNode(pHead1,pHead2);return pHead1;}/**长度统计法长度统计法的思路就是让两个链表分别走，长度差然后在判断两个链表的节点是否相等？如果相等 则直接返回*/public ListNode getLengthSum(ListNode pHead1, ListNode pHead2) {int p1 = this.getLength(pHead1);int p2 = this.getLength(pHead2);if (p1 > p2) {for (int i = 0; i < p1 - p2; i++) pHead1 = pHead1.next;} else {for (int i = 0; i < p2 - p1; i++) pHead2 = pHead2.next;}while ((pHead1 != null) && (pHead2 != null) && (pHead1.val != pHead2.val)) {pHead1 = pHead1.next;pHead2  = pHead2.next;}return pHead1;}/**获取链表的长度*/public int getLength(ListNode pHead) {int n = 0;while (pHead != null) {pHead = pHead.next;n++;}return n;}}

方案二：双指针连接法

第二种方案是，需要两个指针 p1,p2 先去让p1 遍历 pHead1,让 p2遍历 pHead2，当p1遍历完毕之后重新遍历pHead2，反之 p2 则取遍历 pHead1 然后，当两个遍历再某个节点时，遇到了相同的值，那么后续的节点就是链表的相同部分。

这里假设 pHead1的长度是 x, pHead2的长度是 y。公共部分部分的长度是 z。那么 p1,p2走过的长度都是 x+y+z ，所一定会在某个地方值是一样的。此时这个节点就是第一个公共节点。

import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {// 方案一 双指针连接法// pHead1 = this.getNode(pHead1, pHead2);return pHead1;}/**双指针连接法*/public ListNode getNode(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;}
}