每日一题(链表类)——相交链表（Java版）

大数据的奇妙冒险 2022-03-16

177

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。要求返回 c1 这个节点。

解法一

先得到两条链表的长度差 offset，再将长链表跳过 offset 个节点，然后再让这两个链表轮流逐个遍历节点，直到相遇。

比如上图 A 和 B 差一个长度差为 1，先跳过 b1 这个结点到达 b2，然后 A 开始从 a1 遍历，到达 a2， B 到达 b3；随后 A 到达 c1，B 到达 c1，两点相遇，返回 c1.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null)
            return null;


        int lengthA = getListLength(headA);
        int lengthB = getListLength(headB);
        ListNode longList = headA;
        ListNode shortList = headB;
        int offset = Math.abs(lengthA - lengthB);
        if(lengthA < lengthB){
            longList = headB;
            shortList = headA;
        }
        for(int i=0; i < offset; i++){
            longList = longList.next;
        }
        while(shortList != longList){
            shortList = shortList.next;
            longList = longList.next;
        }
        return shortList;
    }
    public int getListLength(ListNode p){
        int length = 0;
        while(p != null){
            length++;
            p = p.next;
        }
        return length;
    }
}
复制

解法二

两条链表先遍历一轮（消除长度差），当链表到达结尾的时候，反而让到达链表末尾的节点指向另一个链表的头部，然后再接着遍历，这样就消除了两条链表的长度差，可以大致理解为：两个人以同样的速度跑步，跑的路程也一致，那么肯定会同一个时间点到达终点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}
复制

java

文章转载自大数据的奇妙冒险，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

每日一题(链表类)——相交链表（Java版）

评论

相关阅读