算法：两个无环单链表的交点

问题描述：

image

题目给定信息：题目中给出两个链表，这两个链表有一部分节点是相互重合的，我们的目的就是要找到两个链表重合的第一个节点，这里需要注意的是链表重合，而不是两个链表的元素相同。

问题分析：

image.png image.png image.png

函数实现：

第一种方法：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int headA_len = Link_len(headA);
        int headB_len = Link_len(headB);
        int move_len = (headA_len > headB_len) ? (headA_len - headB_len)
                : (headB_len - headA_len);
        if (headA_len > headB_len) {
            headA = moveHead(headA, move_len);
        } else {
            headB = moveHead(headB, move_len);
        }
        while (headA != null && headB != null) {
            if(headA==headB){
                return headA;
            }
            headA=headA.next;
            headB=headB.next;
        }
        return null;
    }
    // 计算链表长度的函数
    public int Link_len(ListNode head) {
        int link_len = 0;
        while (head != null) {
            link_len++;
            head = head.next;
        }
        return link_len;
    }

    // 将某一个链表头指针向前移动指定长度的函数
    public ListNode moveHead(ListNode head, int m) {
        while (head != null && m != 0) {
            head = head.next;
            m--;
        }
        return head;
    }

第二种方法：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if(set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }

第三种方法：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头, 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }
        return pA;
    }
}