题目描述：输入两个链表，找出它们的第一个公共结点。

节点类：

public class ListNode {
	int val;
	ListNode next = null;

	ListNode(int val) {
		this.val = val;
	}
}

问题分析：

首先要理解什么是公共节点，并不是两个节点的值相同就是公共节点。

而是在第一链表和第二链表中都存在一个节点，该节点往后的子链表在两个链表中是相同的。

如下图中链表6 - 7就是两个链表的公共链表，而节点6就是第一个公共节点。

方法一：穷举遍历

最直观就是暴力法，在第一链表上顺序遍历每个节点，每遍历到一个节点，就在第二个链表上顺序遍历每个节点。如果在第二个链表上有一个节点和第一个链表上的节点一样，则说明两个链表在这个节点上重合，但是这种方法的时间复杂度为 O(m∗n)（第一个链表长度为m，第二个链表的长度为n）

方法二：栈顶实现

如果两个链表存在公共节点，那么公共节点出现在两个链表的尾部。

如果我们从两个链表的尾部开始往前比较，那么最后一个相同的节点就是我们要找的节点。但是这两个链表是单向的，要实现尾节点最先比较，我们可以借助两个辅助栈。分别将两个链表的节点放入两个栈中，这样栈顶就是两个链表的尾节点，比较两个栈顶节点是否相同，如果相同，将栈顶弹出比较下一个栈顶，直到找到最后一个相同的栈顶。

时间复杂度 O(m + n)

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
	
	if(pHead1 == null || pHead2 == null) {
		return null;
	}
	Stack<ListNode> pStack1 = new Stack<ListNode>();
	Stack<ListNode> pStack2 = new Stack<ListNode>();
	while(pHead1 != null) {
		pStack1.add(pHead1);
		pHead1 = pHead1.next;
	}
	while(pHead2 != null) {
		pStack2.add(pHead2);
		pHead2 = pHead2.next;
	}
	ListNode temp = null;
	while(!pStack1.isEmpty() && !pStack2.isEmpty()) {
		ListNode pH1 = pStack1.pop();
		ListNode pH2 = pStack2.pop();
		if(pH1.val == pH2.val) {
			temp = pH1;		
		}
		else {
			break;
		}
	}
	return temp;

}

方法三：先走一步，链表等长比较

先获得两个链表的长度，然后在较长的链表上先走若干步(两链表长度之差)，接着同时在两个链表上遍历，找到的第一个相同的节点就是他们的第一个公共节点。时间复杂度O(m + n)

public ListNode FindFirstCommonNode_2(ListNode pHead1, ListNode pHead2) {
	if(pHead1 == null || pHead2 == null) {
		return null;
	}
	
	int pHead1Length = getListLength(pHead1);
	int pHead2Length = getListLength(pHead2);
	
	int gap = pHead1Length - pHead2Length;
	ListNode tempList1 = pHead1;
	ListNode tempList2 = pHead2;
	
	if(pHead2Length > pHead1Length) {
		tempList1 = pHead2;
		tempList2 = pHead1;
		gap = pHead2Length - pHead1Length;
	}
	
	for (int i = 0; i < gap; i++) {
		tempList1 = tempList1.next;
	}
	
	while((tempList1 != null) && (tempList2 != null) && (tempList1.val != tempList2.val)) {
		tempList1 = tempList1.next;
		tempList2 = tempList2.next;
	}
	
	return tempList1;

}

public int getListLength(ListNode list) {
	int number = 0;
	while(list != null) {
		++number;
		list = list.next;
	}
	return number;
}

方法四：直接比较指针

用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点。

public ListNode FindFirstCommonNode_3(ListNode pHead1, ListNode pHead2) {
	if(pHead1 == null || pHead2 == null) {
		return null;
	}
	ListNode temp1 = pHead1;
	ListNode temp2 = pHead2;
	while(temp1 != temp2) {
		temp1 = (temp1 == null ? pHead2 : temp1.next);
		
		temp2 = (temp2 == null ? pHead1 : temp2.next);
		System.out.println(pHead1.val);
	}
	
	return temp1;
}

寻找两个单链表的公共结点 （ C语言实现 ）

题目描述：给定两个单链表，编写算法找出两个链表的公共结点

解题思路：

如果两个链表有公共结点，那么必定是链表的末尾部分重合。考虑到链表长度不相同的情况，我们可以先求得两个链表的长度之差dist，让长的链表先走dist步，接着就可以进行同步比较了，当比较出的结点相同时，则意味着该结点为公共结点。

解决的方法可以分为如下三步：

1）求两表长度长度之差dist

2）让长的链表下走dist

3）开始进行同步比较，遇到相同结点即为公共结点

C语言实现代码：

node* get_common_node(node* a, node* b) {
	unsigned int lena = getlen(a);
	unsigned int lenb = getlen(b);
	int dist = lena - lenb; 		// get the dist len between a and b.
	node *longlist, *shortlist;

	if (dist >= 0) {
		longlist = a;
		shortlist = b;
	} else {
		dist = -dist;
		longlist = b;
		shortlist = a;
 	}

	while (dist--) { // the longer list take 'dist' step first.
		longlist = longlist->next;
	}

	while (longlist != NULL) {
		if (longlist == shortlist)
			return longlist;
		longlist = longlist->next;
		shortlist = shortlist->next;
	}

 	return NULL; 	// no common nodes
}

找两个链表的公共节点 （链表环实现）

首先考虑两个链表无环的情况。

将链表a的尾节点指向头节点从而形成环。用快慢指针遍历链表b，一个一次移动2单位，另一个移动1单位。如果不相遇则不存在公共节点。如果相遇，则让其中一个指针指向b，两个指针以1单位/次的速度移动，直到相遇。相遇时指向的节点就是公共节点的起始。最后记得将a的尾节点恢复。代码如下。

其次考虑有环的情况。用快慢指针探测a中是否有环。如果有则，将使p指向a的尾节点，p的next指向null。按照上面的方法遍历b。如果遍历的过程中遇到p，则将p指向a继续遍历。如果未遇到p或者无环，则不存在公共节点。最后仍然将a的尾节点恢复。

static class LinkedList {
	LinkedList next;
	public LinkedList(LinkedList next) {
		this.next = next;
	}
}

static LinkedList calc(LinkedList a, LinkedList b) {
	// set tail point to a
	LinkedList p = a;
	while (p.next != null) {
		p = p.next;
	}
	p.next = a;

	if (b == null || b.next == null)
		return null;
	LinkedList fast = b.next.next, slow = b.next;
	while (fast != null && fast.next != null && fast != slow) {
		fast = fast.next.next;
		slow = slow.next;
	}
	if (fast != slow) {
		return p.next = null;
	} else {
		slow = b;
		while (fast != slow) {
			fast = fast.next;
			slow = slow.next;
		}
		p.next = null;
		return slow;
	}
}

public static void main(String[] args) {
	LinkedList common = new LinkedList(new LinkedList(new LinkedList(null)));
	LinkedList a = new LinkedList(new LinkedList(common));
	LinkedList b = new LinkedList(new LinkedList(new LinkedList(
			new LinkedList(common))));
	LinkedList r = calc(a, b);
	System.out.println(r == common);
}

参考推荐：

两个链表的第一个公共结点

寻找两个单链表的公共结点

找两个链表的公共节点