链表相交问题

题目

给定两个单链表的头结点 head1 和 head2 , 这两个链表可能有环也可能无环, 请判断这两个链表是否相交, 若相交则返回第一个相交结点

要求

如果链表的长度分别为 M 和 N , 时间复杂度为 O(M+N) , 额外空间复杂度为 O(1)

题解

可采用先将一个链表中的结点放入 HashSet 中, 再遍历另一个链表判断结点是否已在该 HashSet 中的方法, 但额外空间复杂度不符合条件.

不使用 HashSet 的解法:

先判断链表是否有环

1. 若链表无环

   此时若两链表相交则至少共用两链表的最后一个结点, 只需判断两链表的最后一个结点是否相同即可. 若要找到第一个相交结点需先统计链表长度 L1 和 L2 , 较长的链表的指针先移动 abs(L1-L2) 步, 剩余的部分即与较短的链表长度相同, 再同时移动相同步数后即可找到第一个相交结点.

   

2. 若一个链表有环一个无环

   此时对两个单链表来说二者不可能相交

   

3. 若两个链表都有环

   此时有三种情况

   

   • 若两个链表的入环结点相同, 则为图2
   • 若另两个链表的入环结点不同, 则可能有图 1 和图 3 两种可能. 可从一个入环结点开始继续遍历, 若再次遍历回该结点之前经过了另一个入环结点则为图 3 情况, 否则为图 1 情况, 即二者不相交.

Java

class ListNode {
    int val;
    ListNode next;

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

public class IntersectionList {
    public static ListNode getEntrance(ListNode head) {
        if (head == null || head.next == null || head.next.next == null)
            return null;

        ListNode slow = head.next;
        ListNode fast = head.next.next;

        while (slow != fast) {
            if (fast.next == null || fast.next.next == null)
                return null;
            slow = slow.next;
            fast = fast.next.next;
        }

        fast = head;

        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    /**
     * 当 entranceA 和 entranceB 设为 null 时, 为求两个无环链表的交点,
     * 当 entranceA 和 entranceB 不为 null 时, 为求交点在入环结点前的两个链表的交点
     *
     * @param headA     链表 1 的头结点
     * @param entranceA 链表 1 的入环结点, 若无环则为 null
     * @param headB     链表 2 的头结点
     * @param entranceB 链表 2 的入环结点, 若无环则为 null
     * @return 两链表的交点
     */
    public ListNode getNodeHelper1(ListNode headA, ListNode entranceA, ListNode headB, ListNode entranceB) {
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        int count = 0;

        while (tmpA != entranceA) {
            count++;
            tmpA = tmpA.next;
        }

        while (tmpB != entranceB) {
            count--;
            tmpB = tmpB.next;
        }

        if (tmpA != tmpB)
            return null;

        // 无论 A 和 B 谁长都能保证 tmpA 始终指向长的, tmpB 指向短的
        tmpA = count > 0 ? headA : headB;
        tmpB = tmpA == headA ? headB : headA;
        count = count > 0 ? count : -count;

        // 将长的链表指针拨到与另一条链表等长处
        while (count != 0) {
            count--;
            tmpA = tmpA.next;
        }

        while (tmpA != tmpB) {
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }

        return tmpA;
    }

    /**
     * 当两链表均有环且入环结点不同, 即两链表交点在环上时
     *
     * @param entranceA 链表 1 入环结点
     * @param entranceB 链表 2 入环结点
     * @return 两链表交点
     */
    public ListNode getNodeHelper2(ListNode entranceA, ListNode entranceB) {
        ListNode tmpA = entranceA.next;

        while (tmpA != entranceA) {
            if (tmpA == entranceB)
                return tmpA;
            tmpA = tmpA.next;
        }

        return null;
    }

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

        ListNode entranceA = getEntrance(headA);
        ListNode entranceB = getEntrance(headB);

        // 两链表均无环
        if (entranceA == null && entranceB == null) {
            return getNodeHelper1(headA, null, headB, null);
        }

        // 两链表均有环
        if (entranceA != null && entranceB != null) {
            // 两链表入环结点相同, 交点在入环结点前或与入环结点重合
            if (entranceA == entranceB) {
                return getNodeHelper1(headA, entranceA, headB, entranceB);
            }

            // 两链表交点在环上(此时两个入环结点均可为交点, 情况 3), 或两个带环链表无交点(情况 1)
            return getNodeHelper2(entranceA, entranceB);
        }

        // 一个链表有环, 一个链表无环, 不可能相交, 直接返回
        return null;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class IntersectionList:
    def get_entrance(self, head):
        if head and head.next and head.next.next:
            slow = head.next
            fast = head.next.next

            while slow != fast:
                if fast.next and fast.next.next:
                    slow = slow.next
                    fast = fast.next.next
                else:
                    return None

            fast = head
            while slow != fast:
                slow = slow.next
                fast = fast.next

            return fast
        else:
            return None

    def get_length(self, head, entrance):
        count = 0
        while head and head != entrance:
            count += 1
            head = head.next

        return count, head

    def get_node_helper1(self, head_a, head_b, entrance_a=None, entrance_b=None):
        length_a, tail_a = self.get_length(head_a, entrance_a)
        length_b, tail_b = self.get_length(head_b, entrance_b)

        tmp_a = head_a if length_a > length_b else head_b
        tmp_b = head_b if tmp_a == head_a else head_a
        steps = abs(length_a - length_b)

        while steps != 0:
            steps -= 1
            tmp_a = tmp_a.next

        while tmp_a != tmp_b:
            tmp_a = tmp_a.next
            tmp_b = tmp_b.next

        return tmp_a

    def get_node_helper2(self, entrance_a, entrace_b):
        tmp_a = entrance_a.next

        while tmp_a != entrance_a:
            if tmp_a == entrace_b:
                return tmp_a
            tmp_a = tmp_a.next

        return None

    def get_intersection_node(self, head_a, head_b):
        if head_a and head_b:
            entrance_a = self.get_entrance(head_a)
            entrance_b = self.get_entrance(head_b)

            if not entrance_a and not entrance_b:
                return self.get_node_helper1(head_a, head_b)

            if entrance_a and entrance_b:
                if entrance_a == entrance_b:
                    return self.get_node_helper1(head_a, head_b, entrance_a, entrance_b)

                return self.get_node_helper2(entrance_a, entrance_b)
        else:
            return None

例题 LeetCode # 160

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

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

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

Java

class ListNode {
    int val;
    ListNode next;

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

public class IntersectionList {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        int count = 0;

        while (tmpA != null) {
            count++;
            tmpA = tmpA.next;
        }

        while (tmpB != null) {
            count--;
            tmpB = tmpB.next;
        }

        if (tmpA != tmpB)
            return null;

        // 无论 A 和 B 谁长都能保证 tmpA 始终指向长的, tmpB 指向短的
        tmpA = count > 0 ? headA : headB;
        tmpB = tmpA == headA ? headB : headA;
        count = count > 0 ? count : -count;

        // 将长的链表指针拨到与另一条链表等长处
        while (count != 0) {
            count--;
            tmpA = tmpA.next;
        }

        while (tmpA != tmpB) {
            tmpA = tmpA.next;
            tmpB = tmpB.next;
        }

        return tmpA;
    }
}

Python

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class IntersectionList:
    def get_length(self, head):
        count = 0
        while head:
            count += 1
            head = head.next

        return count, head

    def getIntersectionNode(self, head_a, head_b):
        length_a, tail_a = self.get_length(head_a)
        length_b, tail_b = self.get_length(head_b)

        tmp_a = head_a if length_a > length_b else head_b
        tmp_b = head_b if tmp_a == head_a else head_a
        steps = abs(length_a - length_b)

        while steps != 0:
            steps -= 1
            tmp_a = tmp_a.next

        while tmp_a != tmp_b:
            tmp_a = tmp_a.next
            tmp_b = tmp_b.next

        return tmp_a