LeetCode160.相交链表

问题描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

方法一

算法思想

使用双指针
当两个链表headA和headB都不为null时，两个链表才可能相交，如果有一个链表为空，两个链表就不可能相交，所以首先应该判断两个链表是否为空，有一个为空，则返回null。
如果两个链表都不为空，则创建两个指针pA和pB，初始时两个指针分别指向两个链表的头结点headA和headB，然后将两个指针分别遍历两个链表的每个结点。
具体步骤如下：
①每步操作需要同时移动指针pA和pB。
②如果指针pA不为空，将指针更新到下一个结点；如果指针pB不为空，将指针更新到下一个结点。
③如果指针pA为空，则将指针pA移到链表headB的头结点；如果指针pB为空，则将指针pA移到链表headA；
④当指针pA和pB指向同一个结点或者都为null时，循环结束，返回他们指向的结点或者null。

动画演示

代码演示

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

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

        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

算法分析

时间复杂度 O(m + n)，其中 m 和 n 分别是链表headA和headB的长度。两个指针同时遍历两个链表，每个链表各被遍历一次。
空间复杂度 O(1)。

方法二

算法描述

同方法一也是采用双指针法。
当两个链表headA和headB有一个为null时，直接返回null。
如果两个链表都不为空，具体步骤如下：
①分别遍历两个链表，得到链表headA的长度count1，链表headB的长度count2。
②创建两个指针p1和p2，比较count1和count2，使指针p1指向较长的链表，指针p2指向较短的链表。
③计算两个链表的长度差diff，然后让指针p1先往后遍历diff个结点。
④同时移动指针p1和p2。当指针p1和p2指向同一个结点或者都为null时，循环结束，返回他们指向的结点或者null。

代码演示

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

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

        ListNode p1;
        ListNode p2;

        int count1 = 0;
        int count2 = 0;
        for(ListNode p = headA; p != null;p = p.next) {
            count1++;
        }

        for(ListNode p = headB; p != null;p = p.next) {
            count2++;
        }

        p1 = count1 > count2 ? headA : headB;
        p2 = count1 > count2 ? headB : headA;
        int diff = Math.abs(count1 - count2);
        while(diff-- > 0) {
            p1 = p1.next;
        }

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