目录

• 2024-03-12 leetcode写题记录
  • 160. 相交链表
    • 题目链接
    • 题意
    • 解法
      • 解法一
      • 解法二

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;
    }
};