目录

2024-03-12 leetcode写题记录

160. 相交链表

题目链接

160. 相交链表

题意

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

图示两个链表在节点\(c1\)开始相交:

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

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

节点定义:

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

解法

解法一

刚看到这道题,想了下数学公式。

一、先遍历一遍A和B,看结尾是否相同,不同则意味着没有公共部分,返回nullptr。

二、如果结尾相同,设A链独有的长度为a,B链独有的长度为b,共有的长度为c。

(1)先从A开头遍历一遍,得到长度x,则x=a+c,同时反转整个A链;

(2)再从从B开头遍历一遍,得到长度y,则y=a+b,同时反转现在的链(即A独有部分和B独有部分串起来);

(3)最后从公共结尾开始遍历,得到长度z,则z=b+c,同时反转整个链(也就是整个B链),那么图形会变成初始模样。

可以得到:
\( \left\{ \begin{aligned} a+c=x\\ a+b=y\\ b+c=z \end{aligned} \right. \)

所以,A链独有部分的长度为\(\frac{x+y-z}{2}\),根据长度返回对应点就行

当没有公共点时,上述式子第二个等式不成立,所以不等式组是错误的,不能直接计算出长度,这也是为什么要分两种情况讨论,而不是直接求出c的长度判断是否为0。

class Solution {
   public:
    // 查链有多长,还可以选择是否反转链表
    int f(ListNode*& head, bool rvs = false) {
        int cnt = 0;
        ListNode *last = nullptr, *to = nullptr;
        while (head != nullptr) {
            cnt++;
            to = head->next;
            if (rvs) head->next = last;
            last = head;
            head = to;
        }
        head = last;
        return cnt;
    }

    ListNode* getLast(ListNode* x) {
        ListNode* last = nullptr;
        while (x != nullptr) {
            last = x;
            x = x->next;
        }
        return last;
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (getLast(headA) != getLast(headB)) return nullptr;
        ListNode *ha = headA;
        int x = f(headA, true), y = f(headB, true), z = f(headA, true), a = (x + y - z) / 2;
        while (a--) ha = ha->next;
        return ha;
    }
};

解法二

看评论区,有更巧妙的想法:

如果两个链有相交,那么可以让两个指针分别从两个链开端进行遍历,每个指针遍历结束之后,都让指针跳到另一个链的开端继续遍历,这样当两个指针相同时,他们就都遍历了整个图,并且相聚在相交点。

两种写法时间复杂度上一样,但解法二写起来简单得多。

class Solution {
   public:
    ListNode* getLast(ListNode* x) {
        ListNode* last = nullptr;
        while (x != nullptr) {
            last = x;
            x = x->next;
        }
        return last;
    }

    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (getLast(headA) != getLast(headB)) return nullptr;
        ListNode *a = headA, *b = headB;
        while (a != b) {
            a = a == nullptr ? headB : a->next;
            b = b == nullptr ? headA : b->next;
        }
        return a;
    }
};