【leetcode100-022】【链表/双指针】相交链表

2023-12-27 21:05:26

【题干】

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

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

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

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

【思路】

复试前写过这题,今天又碰上了,心情belike:

琢磨了很久终于想起来了,是那个很浪漫的链表相交。

  • 首先,不难想到,如果有相交节点,那么对两个链表各自来说,该节点距离链表尾的距离肯定是相同的;
  • 然后自然会想到,先统计一下节点数量,然后长的先走几步,接着两个指针一起走之类的,太常规了就不写一遍代码了;
  • 虽然A和B不一定等长,但是,如果让两个指针都把A+B(B+A)走一遍,当它们都进入各自的第二条链时,距离末尾的长度就一定相等啦!

【题解】

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *A = headA, *B = headB;
        while (A != B) {
            A = A != nullptr ? A->next : headB;
            B = B != nullptr ? B->next : headA;
        }
        return A;
    }
};

文章来源:https://blog.csdn.net/weixin_63059689/article/details/135251196
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。