本文共 1053 字，大约阅读时间需要 3 分钟。

题目：两个链表的第一个公共结点

题目描述 输入两个链表，找出它们的第一个公共结点。 解题思路： （1）借助辅助栈 （2） 通过两个链表长度特点：不用借助辅助栈，提高空间效率 第二种方案：通过两个链表长度特点 首先需要进行分析的是有公共节点的两个链表有哪些特征？ 从链表节点的定义可以看出，这两个链表都是单向链表。如果两个单向链表有公共节点， 那么这连个链表从某一个节点开始，他们的next都指向同一个节点。但由于是单向链表的节点， 每个节点直邮一个next，因此从第一个公共节点开始，之后他们所在的节点都是重合的，不可能出现分叉。所以两个有公共节点而部分重合的链表，拓扑形状看起来像是个Y ,而不可能是个X 解题思路：分别找到两个链表的长度，pHead1的长度len1,pHead2的长度len2。 如果int diff=len1-len2>0;说明pHead1的长度大于pHead2，让pHead1先走diff步，使它和pHead2处于同样的长度； 如果int diff=len1-len2<0;说明pHead1的长度小于pHead2，让pHead2先走diff步，使它和pHead1处于同样的长度 长度相等直接判断，如果两个节点相等，返回，不等，接着往下走，走到头还没有，返回null 代码实现：

/*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 cur1=pHead1;		ListNode cur2=pHead2;		//遍历两个链表得到他们的长度		int len1=0;		while(cur1!=null) {			len1++;			cur1=cur1.next;		}		int len2=0;		while(cur2!=null) {			len2++;			cur2=cur2.next;		}		//知道哪个链表比较长，以及唱的链表比短的链表多几个节点		int diff=len1-len2;		//在较长的链表上走上若干步		if(diff>=0) {			for(int i=0;i

转载地址：http://ldhq.baihongyu.com/