讨论/《算法面试题汇总》 - 相交链表/
《算法面试题汇总》 - 相交链表
共 1 个回复
  1. 第一想到的是暴力算法,遍历A 的每个节点,再遍历B 去检查是否 A 在B 中,时间复杂度 O(m * n),空间复杂度O(1),不满足时间复杂度要求。
  2. 用Set,遍历A,把每个数字与元素set中,再遍历B,检查Set 中是否存在,如果存在,那就是相交点,时间复杂度O(m +n),空间复杂度 O(m) 或O(n),不满足空间复杂度要求
  3. 这个比较像单链表中找环,假设他们相交,只要把尾节点和其中一个头节点连接,这就变成了一个有环的列表中找入口点的问题,接下来就是用快慢指针来找了,找到以后再把尾节点到头结点的连接解除。时间复杂度O(m +n),空间复杂度O(1)

`public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tailA = headA;
ListNode tailB = headB;
int sizeA = 0;
int sizeB = 0;
while (tailA.next != null){
tailA = tailA.next;
sizeA ++;
}

    while (tailB.next != null){
        tailB = tailB.next;
        sizeB ++;
    }

    if (tailA != tailB){
        // 没有相交
        return null;
    }

    ListNode head;
    if (sizeA < sizeB){
        // 较短的连成环
        tailA.next = headA;
        head = headB;
    }
    else {
        tailB.next = headB;
        head = headA;
    }

    // 计算链表中环的开始位置
    ListNode fast = head;
    ListNode slow = head;
    while (true){
        fast = fast.next.next;
        slow = slow.next;
        
        // 快慢指针相遇
        if (fast == slow){
            fast = head;
            while (fast != slow){
                fast = fast.next;
                slow = slow.next;
            }
            
            tailA.next = null;
            return fast;
        }
    }
}

}`