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

题目：

输入两个链表，找出他们的第一个公共节点。

输入：

单链表A：4，3，2，1，单链表：3，2，1

输出：

3

解题思路：

1、得到两个链表的长度，链表A减去链表B的长度得到变量DPSLength。

2、如果变脸DpsLength大于0，则链表A往前走DPSLength步，否则，链表B往前走DPSLength步。

3、接下来，两个链表同时遍历，直到找到相同的节点。

4、（没有写的解法）当然还有另外一种解法是需要利用辅助栈的，因为根据两个链表的特点，公共节点是出现在两个链表尾部的，只需要遍历一遍把他存入栈中，然后不停的再从栈中取出来，对比两个节点是否相同，那么公共节点由于是后进先出的缘故，所以，他一定是栈中最后一个相同的公共节点，这个节点就是我们要找的节点了。

Java实现代码：

public static void main(String[] args) {
		// TODO Auto-generated method st
		Linked linkeder=new Linked();
		LinkNode node1=new LinkNode(1);
		LinkNode node2=new LinkNode(2);
		LinkNode node3=new LinkNode(3);
		LinkNode node4=new LinkNode(4);
		linkeder.insertFirst(node1);
		linkeder.insertFirst(node2);
		linkeder.insertFirst(node3);
		linkeder.insertFirst(node4);


		Linked linked2=new Linked();
	linked2.insertFirst(node1);
	linked2.insertFirst(node2);
	linked2.insertFirst(node3);
	System.out.println(findFirstComonNode(linkeder, linked2).data);

	}



	private static LinkNode findFirstComonNode(Linked head1,Linked head2){
		int nLnegth1=head1.getListSize();
		int nLnegth2=head2.getListSize();

		int dpsLength=nLnegth1-nLnegth2;
		LinkNode node1=head1.header;  //Long
		LinkNode node2=head2.header;  //shart

		if(nLnegth2>nLnegth1){
			dpsLength=nLnegth2-nLnegth1;
			 node1=head2.header;
			 node2=head1.header;
		}

		for(int i=0;i<dpsLength;i++){
			node1=node1.next;
		}

		while(node1!=null && node2!=null && node1!=node1){
			node1=node1.next;
			node2=node2.next;
		}
		LinkNode nodeCommon=node1;
		return nodeCommon;
	}