作业：链表交叉点

 关注
发布于: 2020 年 07 月 29 日
解题思路：
如果两个链表存在交叉点的话，图形如下：
意味着在交叉点之后，两个链表的节点是一样的。这就意味着如果两个链表不一样长的话，长的链表多出来的节点，针对上图就是指d肯定不可能是交叉点，所以，解题方案就是跳过长链表多出来的部分，从e开始与短链表从a开始，逐个节点进行比较，如果节点相同即为交叉节点，具体的代码如下：
构建节点对象，代码如下：
    static class Node {
        private int value;
        private Node next;
        public Node(int value) {
            this.value = value;
        }
        public int getValue() {
            return value;
        }
        public Node getNext() {
            return next;
        }
        public void setNext(Node next) {
            this.next = next;
        }
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }
﻿
求两个链表的交叉点，方法如下：
    public static Node findIntersection(Node head1, Node head2) {
        int size1 = sizeOf(head1);
        int size2 = sizeOf(head2);
        if (size1 == 0 || size2 == 0) {
            return null;
        }
        Node longHead = null;
        Node shortHead = null;
        int offset = size1 - size2;
        if (offset >= 0) {
            longHead = head1;
            shortHead = head2;
        } else {
            longHead = head2;
            shortHead = head1;
            offset = -offset;
        }
        Node lcNode = longHead;
        Node scNode = shortHead;
        if (offset > 0) {
            int count = 1;
            lcNode = lcNode.getNext();
            while (offset > count) {
                lcNode = lcNode.getNext();
                count++;
            }
        }
        while (lcNode != null) {
            if (lcNode.getValue() == scNode.getValue()) {
                return lcNode;
            }
            lcNode = lcNode.getNext();
            scNode = scNode.getNext();
        }
        return null;
    }
   private static int sizeOf(Node head) {
        if (head == null) {
            return 0;
        }
        int size = 1;
        Node start = head;
        while (start.getNext() != null) {
            size++;
            start = start.getNext();
        }
        return size;
    }
客户端代码如下：
    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);
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        node5.setNext(node6);
        node6.setNext(node7);
        node7.setNext(node8);
        node8.setNext(node9);
        Node node11 = new Node(11);
        Node node22 = new Node(22);
        Node node33 = new Node(33);
        node11.setNext(node22);
        node22.setNext(node33);
        node33.setNext(node6);
        
        Node intersection = findIntersection(node11, node1);
        System.out.println(intersection);
    }
最后的打印输出结果如下：
Node{value=6}
﻿