面试题52：两个链表的第一个公共结点

题目：

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

分析：

首先画两个包含公共结点的链表，观察它们的形状，它们的形状是Y型的，在某一个结点重合后，后面的结点都是重合的。将两个链表分别入栈，因为两个链表尾部相同，对应到栈中，就是栈顶有一部分元素一一相等，依次将它们出栈，直到最后一个相等的元素为止，此时这个元素就是第一个公共子结点了。

还有一个方案，先把两个链表的长度统计出来，计算它们的长度差，让长的链表先走这个差值的长度的，然后长短链表一起走，并比较它们的值是否相同，直到碰到第一个相同的元素为止。

解法：

package com.wsy;

import java.util.Stack;

class Node {
    private int value;
    private Node next;

    public Node() {
    }

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

public class Main {
    public static void main(String[] args) {
        Node head1 = init1();
        Node head2 = init2();
        getFirstCommonNode(head1, head2);
        getFirstCommonNodeByLength(head1, head2);
    }

    public static Node init1() {
        Node node7 = new Node(7, null);
        Node node6 = new Node(6, node7);
        Node node3 = new Node(3, node6);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        return node1;
    }

    public static Node init2() {
        Node node7 = new Node(7, null);
        Node node6 = new Node(6, node7);
        Node node5 = new Node(5, node6);
        Node node4 = new Node(4, node5);
        return node4;
    }

    public static void getFirstCommonNode(Node head1, Node head2) {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        while (head1 != null) {
            stack1.push(head1.getValue());
            head1 = head1.getNext();
        }
        while (head2 != null) {
            stack2.push(head2.getValue());
            head2 = head2.getNext();
        }
        int firstCommonNode = stack1.peek();
        while (true) {
            int node1 = stack1.peek();
            int node2 = stack2.peek();
            if (node1 == node2) {
                firstCommonNode = node1;
                stack1.pop();
                stack2.pop();
            } else {
                break;
            }
        }
        System.out.println("第一个公共结点的值是：" + firstCommonNode);
    }

    public static void getFirstCommonNodeByLength(Node head1, Node head2) {
        int length1 = 0, length2 = 0;
        Node temp = head1;
        while (temp != null) {
            length1++;
            temp = temp.getNext();
        }
        temp = head2;
        while (temp != null) {
            length2++;
            temp = temp.getNext();
        }
        if (length1 > length2) {
            for (int i = 0; i < length1 - length2; i++) {
                head1 = head1.getNext();
            }
        } else {
            for (int i = 0; i < length2 - length1; i++) {
                head2 = head2.getNext();
            }
        }
        while (head1.getValue() != head2.getValue()) {
            head1 = head1.getNext();
            head2 = head2.getNext();
        }
        System.out.println("第一个公共结点的值是：" + head1.getValue());
    }
}