架构师训练营 1 期第 8 周：性能优化（二）- 作业

public class FindCrossNode {

    public static class Node {
        public int data;
        public Node next;

        public Node(int data) {
            this.data = data;
        }
    }

    public static Node findNode(Node head1, Node head2) {

        if(head1 == null || head2 == null) {
            return null;
        }

        Node p1 = head1;
        Node p2 = head2;
        int len1 = 0;
        int len2 = 0;
        int diff = 0;

        //遍历链表1
        System.out.println("单向链表1：");
        while (p1.next != null) {
            System.out.print(p1.data + "->");
            p1 = p1.next;
            len1++;
        }
        len1++;
        System.out.println(p1.data);
        System.out.println("链表1长度：" + len1);

        //遍历链表2
        System.out.println("单向链表2：");
        while (p2.next != null) {
            System.out.print(p2.data + "->");
            p2 = p2.next;
            len2++;
        }
        len2++;
        System.out.println(p2.data);
        System.out.println("链表2长度：" + len2);

        //两个链表尾节点不相等，代表两个链表没有合并
        if(p1 != p2) {
            return null;
        }

        //找到两个链表的合并节点，并返回合并节点
        diff = Math.abs(len1-len2);

        p1 = (len1 > len2)?head1:head2;
        p2 = (len1 > len2)?head2:head1;

        for (int i=0; i<diff; i++) {
            p1 = p1.next;
        }

        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }

    public static void main(String[] args) {
        //初始化节点
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);

        //构建链表
        node1.next = node2;
        node2.next = node3;
        node3.next = node8;

        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;

        node8.next = node9;
        node9.next = node10;

        //找到合并节点
        Node node = findNode(node1, node4);
        System.out.println("合并节点元素值为："+node.data);
    }
}

单向链表1：
1->2->3->8->9->10
链表1长度：6
单向链表2：
4->5->6->7->8->9->10
链表2长度：7
合并节点元素值为：8