两个单链表相交的起始节点

题目描述
找到两个单链表相交的起始节点。
如下面的两个链表:

在节点 c1 开始相交。

注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
复杂度分析

双指针法

核心一点就是得知道,如果不存在环,两个链表相交,那么他们的尾节点一定是相同的。
show code

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null || headB==null){
            return null;
        }
        ListNode aTail=headA;
        ListNode bTail=headB;
        int alength=1;
        int blength=1;
        while(aTail.next!=null){
            aTail = aTail.next;
            alength++;
        }
         while(bTail.next!=null){
            bTail = bTail.next;
            blength++;
        }
        if(!aTail.equals(bTail)){//判断两个链尾是否在是同一个节点,如果相交一定是同一个节点
            return null;
        }
        ListNode shortPonit = headA;
        ListNode longPonit = headB;
        int sub =Math.abs(alength-blength);
        if(alength>blength){
            shortPonit = headB;
            longPonit=headA;
        }
        while(sub>0){//长链表的指针先走sub步,保证未遍历的长度和短链表相等
            longPonit=longPonit.next;
            sub--;
        }
        while(!longPonit.equals(shortPonit)){//移动到第一个相等的节点,即为交点
            longPonit = longPonit.next;
            shortPonit=shortPonit.next;
        }
        return shortPonit;
    }

上面代码比较直观,但是略显啰嗦。
可以换个方式消除长度差:拼接两链表。
如图,两指针分别先后遍历两链表第一个相等的点就是相交点。

show code

  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode apointer = headA;
        ListNode bpointer = headB;
        while(apointer != bpointer){
            apointer = (apointer == null ? headB : apointer.next);
            bpointer = (bpointer == null ? headA : bpointer.next);
        }
        return apointer;
    }

时间复杂度 : O(m+n)
空间复杂度 : O(1)

其他解法

问题转化为判断一个链表是否有环问题

这个问题我们可以转换为另一个等价问题:如何判断一个单链表是否有环,若有环,找出环的入口?

如何转化?
先遍历第一个链表到它的尾部,然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表。若该链表有环,则原两个链表一定相交。否则,不相交。

暴力法

对链表A中的每一个结点,遍历整个链表B并检查链表B中是否存在结点相同。

复杂度分析
时间复杂度 : (mn)
空间复杂度 : O(1)

哈希表法

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表B中的每一个结点 是否在哈希表中。若在,则为相交结点。

复杂度分析
时间复杂度 : O(m+n)
空间复杂度 : O(m)或 O(n)

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×