【LeetCode】每日一题:链表部分经典题型

这篇具有很好参考价值的文章主要介绍了【LeetCode】每日一题:链表部分经典题型。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode】每日一题:链表部分经典题型

​👻内容专栏:《LeetCode刷题专栏》
🐨本文概括:归纳链表部分经典题型206.反转链表876.链表的中间节点21.合并两个有序链表160.相交链表141.环形链表142.环形链表Ⅱ
🐼本文作者:花 碟
🐸发布时间:2023.5.17

1.反转链表

👉 206.反转链表

题目描述:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例1

【LeetCode】每日一题:链表部分经典题型

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例2
【LeetCode】每日一题:链表部分经典题型

输入:head = [1,2]
输出:[2,1]

👉思想1

对链表进行遍历,改变每个节点的 next 指针指向,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头节点。
时间复杂度为O(N),空间复杂度为O(1)

👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//1.反转链表 改变next指针指向
struct ListNode* reverseList(struct ListNode* head){
    //链表为空
    if(head == NULL)
        return NULL;
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    struct ListNode* Next = head->next;
    //当cur等于空结束
    while(cur)
    {
        //反转
        cur->next = prev;

        //迭代
        prev = cur;
        cur = Next;
        if(Next)
        	Next = Next->next;
    }
    return prev;
}

👉思想2

新建一个rhead节点,使用cur迭代链表,对于每个cur节点从rhead开始插入,每次插入之后,需要更新rhead,最后得到的新链表即为反转之后的链表,由于每每插入一个节点之后,需要继续在原链表进行往后迭代走,所以再定义一个Next指针进行临时存储,头插完后给到cur。

👉图解
【LeetCode】每日一题:链表部分经典题型
👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//2.头插法
struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* rhead  = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* Next = cur->next;
        //头插
        cur->next = rhead;
        rhead = cur;
        
        //迭代
        cur = Next;
    }
    return rhead;
}

2.链表的中间节点

👉 876.链表的中间结点

题目描述: 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。

示例1
【LeetCode】每日一题:链表部分经典题型

输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 

示例2
【LeetCode】每日一题:链表部分经典题型

输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解释:该链表有两个中间结点,值分别为 34 ,返回第二个结点。

👉思想

求链表的中间节点,我们定义两个指针slowfast,核心思想是让slow一次走一步,fast一次走两步,但是这里有两种情况需要分别看待,1️⃣如果有一个中间节点,即链表长度为奇数,那么fast->next为空即为结束条件,2️⃣如果有两个中间节点,即链表长度为偶数,那么fast为空即为结束条件
最后返回slow,就是链表的中间节点

👉图解
【LeetCode】每日一题:链表部分经典题型
👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head){
     struct ListNode* fast = head ,* slow = head;
     while(fast && fast->next)
     {
         //fast一次走两步
         //slow一次走一步
         fast = fast->next->next;
         slow = slow->next;
     }
     return slow;
}

3.合并两个有序链表

👉21.合并两个有序链表

题目描述: 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例1
【LeetCode】每日一题:链表部分经典题型

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例2

输入:l1 = [], l2 = []
输出:[]

示例3

输入:l1 = [], l2 = [0]
输出:[0]

👉思想

⚠️注意此题的提示是链表1和链表2均按非递减的顺序排列。
我们可以拿示例1的图片来看,首先还是新开辟链表头节点head(此时说的是不带哨兵位的头节点,需要多加一个head为空的判断的情况),为了避免head会被修改,我们定义一个tail,让tail进行迭代,然后对链表l1和链表l2中的val值进行比较,值较小的进行尾插,直到有一个链表走向了空,循环就结束,但是如果另外一个链表非空,直接将tail->next指向非空链表的头节点即可。最后返回head
⚠️注意还需要单独考虑list1list2为空的情况

👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* head = NULL,* tail = NULL;
    //链表为空
        if(list1 == NULL)
            return list2;
        if(list2 == NULL)
            return list1;

    //一个链表走向空,循环就结束
        while(list1 && list2)
        {
            if(list1->val > list2->val)
            {
                if(tail == NULL)
                {
                    head = tail = list2;
                }else
                {
                    tail->next = list2;
                    tail = tail->next;
                }
                list2 = list2->next;
            }
            else
            {
                if(tail == NULL)
                {
                    head = tail = list1;
                }else
                {
                    tail->next = list1;
                    tail = tail->next;
                }
                list1 = list1->next;
            }
        }
    //另外一个链表非空,将非空链表头节点给到尾指针
        if(list1)
            tail->next = list1;
        if(list2)
            tail->next = list2;
    return head;
}

4.相交链表

👉160.相交链表

题目描述:
给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null

📌题目提示:
【LeetCode】每日一题:链表部分经典题型
示例1
【LeetCode】每日一题:链表部分经典题型

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at '8'
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。
换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

示例2
【LeetCode】每日一题:链表部分经典题型

输入:intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Intersected at '2'
解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [1,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例3
【LeetCode】每日一题:链表部分经典题型

输入: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 。

👉思想

我们还是需要遍历整个链表,1️⃣需要先进行判断链表是否存在相交节点,那么如何判断两个链表是否是存在相交节点的情况呢?其实很简单,观察下方图解,表示相交的就是第一种和第二种情况,第三种情况是不可能出现的,以及上面的示例3 ,所以我们只需要判断两个链表最后的尾结点是否相同,如果不相同,就说明不存在相交节点,则返回NULL,同时计算两个链表的长度(节点的数量),2️⃣我们需要定义一个longlist 表示较长的链表,定义shortlist 表示较短的链表3️⃣让长度长的longlist链表先迭代走,直到走到和另一个链表的长度相匹配,然后同时往后迭代移动,两个链表地址相等时,循环结束,最后返回任意一个链表地址即可。
时间复杂度:O(N),空间复杂度:O(1)

👉图解
【LeetCode】每日一题:链表部分经典题型

👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    
    int lenA = 1,lenB = 1;
    //计算两个链表节点的数量
    while(tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }
    //
    while(tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }
    //尾结点不相等 链表不存在相交节点,此时返回NULL
    if(tailA != tailB)
    {
        return NULL;
    }
    //假设A链表比B链表长
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;

    int gap = abs(lenA - lenB);
    //否则交换
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }

    //长度大的先走
    while(gap--)
    {
        longList = longList->next;
    }
    //数量相等后 同时往后走
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    //两个地址相等返回任意地址
        return longList;
}

5.环形链表

👉141.环形链表

题目描述:
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况
如果链表中存在环 ,则返回 true 。 否则,返回 false

示例1
【LeetCode】每日一题:链表部分经典题型

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例2
【LeetCode】每日一题:链表部分经典题型

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例3
【LeetCode】每日一题:链表部分经典题型

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

👉思想

快慢指针解法,快指针步数为慢指针步数的两倍,即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,
如果链表带环则一定会在环中相遇,否则快指针率先走到链表的末尾。
这种思路还是模棱两可的小伙伴,可以拿笔在纸上画一画~也许能领悟到了。

👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode * slow = head,* fast = head;
    while(fast && fast->next)
    {
        //慢指针每次走一步
        //快指针每次走两步
        slow = slow->next;
        fast = fast->next->next;
        //快慢指针相遇即链表带环
        if(slow == fast)
            return true;
    }
    //链表不带环
    return false;
}

📌【扩展问题】为什么慢指针每次走1步,快指针每次走2步可以相遇?

假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。当慢指针刚进环时,可能就和快指针相遇了,最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在满指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。

那么慢指针每次走1步,快指针每次走3、4、5……n步行吗?

假设快指针每次走3步,慢指针每次走1步,此时快指针先进入环,慢指针后进入环。假设慢指针进入环的时候,快指针的位置如图所示,
【LeetCode】每日一题:链表部分经典题型
此时按照上述步骤来回是一个绕环运动,快指针每次走3步,慢指针每次走1步,它俩是永远不会相遇的,快指针刚好将慢指针套圈了,因此不一定可行。
那么快指针走其他步数呢?答案都是不一定!
🔖推论fast会先进环,slow会后进环,假设slow进环时,fast与slow之间的距离为N,slow进环之后,fast开始追寻slow,slow每次走1步,fast每次走3步,他们之间的距离缩小2。
如果他们之间的距离N为偶数,那么下次距离为N - 2、N - 4、…… 6、4、2、0,他们可以相遇,但距离N如果为奇数,那么下次距离为N - 2、N - 4、……5、3、1、-1,他们可能会错过。

故:只有快指针每次走2步,慢指针每次走1步才行的通,因为环的最小长度是1,尽可能的让他们之间的步数间距保持为1,即使套圈了,下次也能够相遇。

接下里我们继续来一道相关的变形题👇😇

6.环形链表Ⅱ

👉142.环形链表Ⅱ

题目描述:给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅>仅是为了标识链表的实际情况。不允许修改 链表。

示例1
【LeetCode】每日一题:链表部分经典题型

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例2
【LeetCode】每日一题:链表部分经典题型

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例3
【LeetCode】每日一题:链表部分经典题型

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

👉思想

一个指针从相遇点开始走,一个指针从链表头开始走,他们相遇时,即为入环的第一个节点。

👉 代码实现

 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head;
    struct ListNode * slow  = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //求环的入口点
            struct ListNode * meet = slow;
            while(head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    //链表无环
    return NULL;
}

🔖推理:

这种思想没看懂?我们不妨花五分钟来推理一下:
fast走的路程是slow的2倍。我们假设链表头head到环的入口点的距离为L,假设环的入口点到相遇点meet(即fast第一次追寻上slow)的距离为X,假设环的长度为C,所以我们可以得出slow走的路程为L+X,fast走的路程为L + n*C + X,n为slow在入环前,fast转过环的圈数,也就是说n的大小取决于L和C的长度,n的范围一定是≥1的。
所以我们可以列出一个式子:2(L+X) = L + n*C + X,即L = n*C - X或者看成L = (n- 1)*C + C - X
这里的n*C就是相遇点,减去X后就是入环口,而head走过的L距离之后也正好是入环口,这就应证了我们开始的思想。

👉图解
【LeetCode】每日一题:链表部分经典题型
👉思想2

定义一个meetNext 指针,用来保存相遇点的next,并将meet->next置为NULL。从meetNext开始,与头节点head开始一起遍历,此时可以转换为链表相交问题,相交节点即为环的入口点。

👉 代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;


    int lenA = 1,lenB = 1;
    //计算两个链表节点的数量
    while(tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }
    //
    while(tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }
    //尾结点不相等 链表不存在相交节点,此时返回NULL
    if(tailA != tailB)
    {
        return NULL;
    }
    //假设A链表比B链表长
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;

    int gap = abs(lenA - lenB);
    //否则交换
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }

    //长度大的先走
    while(gap--)
    {
        longList = longList->next;
    }
    //数量相等后 同时往后走
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    //两个地址相等返回任意地址
        return longList;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * fast = head;
    struct ListNode * slow  = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //求环的入口点
            struct ListNode* meet = slow;
            struct ListNode* meetNext = meet->next;
            meet->next = NULL;
            //转换为链表相交问题
            struct ListNode* pos = getIntersectionNode(head,meetNext);
            return pos;
        }
    }
    //链表无环
    return NULL;
}

链表部分题型就到这里,如果对小伙伴们有帮助的话,还请三连支持支持我哦😉😉文章来源地址https://www.toymoban.com/news/detail-450814.html

到了这里,关于【LeetCode】每日一题:链表部分经典题型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Leetcode-每日一题【143.重排链表】

    给定一个单链表  L   的头节点  head  ,单链表  L  表示为: 请将其重新排列后变为:  不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1:     输入: head = [1,2,3,4,5] 输出: [1,5,2,4,3] 提示: 链表的长度范围为  [1, 5 * 104] 1 = node.val = 1000 1.首先我们

    2024年02月11日
    浏览(42)
  • Leetcode-每日一题【61.旋转链表】

    给你一个链表的头节点  head  ,旋转链表,将链表每个节点向右移动  k   个位置。 示例 1: 输入:head = [1,2,3,4,5], k = 2 输出:[4,5,1,2,3] 示例 2:   输入: head = [0,1,2], k = 4 输出: [2,0,1] 提示: 链表中节点的数目在范围  [0, 500]  内 -100 = Node.val = 100 0 = k = 2 * 109 1.根据题目给出

    2024年02月11日
    浏览(36)
  • (链表) 剑指 Offer 24. 反转链表 ——【Leetcode每日一题】

    难度:简单 定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。 示例: 输入 : 1-2-3-4-5-NULL 输出 : 5-4-3-2-1-NULL 限制 : 0 = 节点个数 = 5000 注意:本题与 206. 反转链表 相同。 💡思路: 法一:递归 可以将本问题分解成子问题: 1 - (剩余部分的反转)

    2024年02月15日
    浏览(48)
  • Leetcode-每日一题【1669.合并两个链表】

    给你两个链表 list1 和 list2 ,它们包含的元素分别为 n 个和 m 个。 请你将 list1 中下标从 a 到 b 的全部节点都删除,并将list2 接在被删除节点的位置。 下图中蓝色边和节点展示了操作后的结果:   请你返回结果链表的头指针。 示例 1: 输入: list1 = [0,1,2,3,4,5], a = 3, b

    2024年02月13日
    浏览(49)
  • leetcode每日一题——189.轮转数组(面试经典150题)

    189. 轮转数组 - 力扣(LeetCode) 给定一个整数数组  nums ,将数组中的元素 向右轮转  k   个位置 ,其中  k   是非负数。 示例1: 示例2: 1 = nums.length = 105 -231 = nums[i] = 231 - 1 0 = k = 105        对题目进行分析可知,我们需要根据轮转量k,将数组后面的k个元素按照原来的顺

    2024年02月12日
    浏览(38)
  • 2023-07-29 LeetCode每日一题(环形链表)

    点击跳转到题目位置 给你一个链表的头节点 head ,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:p

    2024年02月15日
    浏览(41)
  • 2023-07-31 LeetCode每日一题(重排链表)

    点击跳转到题目位置 给定一个单链表 L 的头节点 head ,单链表 L 表示为: 请将其重新排列后变为: 不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。 示例 1: 示例 2: 提示: 链表的长度范围为 [1, 5 * 10 4 ] 1 = node.val = 1000 (1) 使用 分治 的思路来解决问题。

    2024年02月14日
    浏览(46)
  • Leetcode-每日一题【147.对链表进行插入排序】

    给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。 插入排序 算法的步骤: 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在

    2024年02月16日
    浏览(37)
  • leetcode每日一题——45.跳跃游戏II(面试经典150题)

    45. 跳跃游戏 II - 力扣(LeetCode) 给定一个长度为 n 的 0 索引 整数数组 nums。 初始位置为 nums[0] 。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:   0 = j = nums[i]     i + j n 返回到达 nums[n - 1] 的最小跳跃次数

    2024年02月13日
    浏览(43)
  • (链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】

    难度:简单 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1: 输入:1-2-4, 1-3-4 输出:1-1-2-3-4-4 限制 : 0 = 链表长度 = 1000 注意:本题与 21. 合并两个有序链表 相同 💡思路: 法一:递归 将该问题可以分解成子链表,只比较当前 l1 链

    2024年02月15日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包