《剑指offer》-寻找两个单链表第一个公共的节点

import java.util.Stack;
/*
 * 找到两个链表第一个公共的节点
 */
class ListNode {
	 int val;
	 ListNode next = null;

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

public class FindFirstCommonNode {
	public ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) {
		if(pHead1 == null || pHead2 == null)	return null;

		//分别统计两个链表的长度
		int length1 = getLength(pHead1);
		int length2 = getLength(pHead2);

		if(length1 > length2){
			int length_diff = length1 - length2;
			//pHead1多走length_diff步
			while(pHead1 != null && length_diff > 0) {
				pHead1 = pHead1.next;
				length_diff --;
			}
		}

		if(length1 < length2){
			int length_diff = length2 - length1;
			//pHead2多走length_diff步
			while(pHead2 != null && length_diff > 0) {
				pHead2 = pHead2.next;
				length_diff --;
			}
		}

		ListNode common_node = null;
		while(pHead1 != null && pHead2 != null) {
			if(pHead1.val == pHead2.val) {
				common_node = pHead1;
				break;
			}

			pHead1 = pHead1.next;
			pHead2 = pHead2.next;

		}

		return common_node;
	}

	public static int getLength(ListNode head) {
		int count = 1;
		while(head.next != null) {
			count ++;
			head = head.next;
		}

		return count;
	}

	//借助栈：以空间换时间，时间复杂度O(M)
	public ListNode findFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
		if(pHead1 == null || pHead2 == null)	return null;

		Stack<ListNode> s1 = new Stack<ListNode>();
		Stack<ListNode> s2 = new Stack<ListNode>();
		while(pHead1 != null) {
			//System.out.print("pHead1:" + pHead1.val + " ");
			s1.push(pHead1);
			pHead1 = pHead1.next;
		}

		while(pHead2 != null) {
			//System.out.print("pHead2:" + pHead2.val + " ");
			s2.push(pHead2);
			pHead2 = pHead2.next;
		}

		ListNode node = null;
		while(!s1.isEmpty() && !s2.isEmpty()) {
			ListNode temp1 = s1.pop();
			ListNode temp2 = s2.pop();
			if(temp1.val == temp2.val) { //如果有公共节点，栈顶元素即链表末尾元素肯定是一直相等的，直到找到第一个不等的元素
				node = temp1;
			}
			else {
				break;
			}
		}

		return node;

	}

	public static void main(String[] args) {
		ListNode node = new ListNode(1);
		node.next = new ListNode(4);
		node.next.next = new ListNode(2);
		node.next.next.next = new ListNode(3);

		ListNode node2 = new ListNode(2);
		node2.next = new ListNode(3);

		ListNode common_node = new FindFirstCommonNode().findFirstCommonNode(node, node2);
		System.out.println(common_node.val);
	}
}