• 【LeetCode】链表OJ题

    ​🌠 作者：@阿亮joy.
    🎆专栏：《阿亮爱刷题》
    🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
    在这里插入图片描述

    目录



    👉复制带随机指针的链表👈

    给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

    构造这个链表的深拷贝。 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random

    指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

    例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有
    x.random --> y 。

    返回复制链表的头节点。

    用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

    • val：一个表示 Node.val 的整数。
    • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码只接受原链表的头节点 head 作为传入参数。

    你的代码只接受原链表的头节点 head 作为传入参数。

    示例1：

    在这里插入图片描述
    输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

    示例2：

    在这里插入图片描述
    输入：head = [[1,1],[2,1]]
    输出：[[1,1],[2,1]]

    提示：

    • 0 <= n <= 1000
    • -10^4 <= Node.val <= 10^4
    • Node.random 为 null 或指向链表中的节点。

    思路：这道题的 next 指针非常容易复制，难就难在怎么复制随机指针。其实这道题有一个很巧妙的思路：第一步，先将复制节点插入到原节点和下一个节点之间，让复制链表和原链表产生链接关系。第二步：根据原节点的 random 指针，处理复制节点的 random 指针。因为复制节点的 random 指针就是原节点的 random 指针的 next。第三步：将复制节点解下来链接成一个新链表，然后恢复原链表的链接关系。
    在这里插入图片描述

    /*
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) 
{
    if(head == NULL)
        return NULL;
    //1.将复制节点插入到原节点和下一个节点之间
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        //插入copy节点
        copy->next = cur->next;
        cur->next = copy;
        //迭代往后走
        cur = copy->next;
    }
    //2.根据原节点的random指针，处理复制节点的random指针
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        //迭代往后走
        cur = copy->next;
    }
    //3.将复制节点解下来链接成一个新链表，然后恢复原链表的链接关系
    //哨兵位头节点
    struct Node* copyHead = (struct Node*)malloc(sizeof(struct Node));
    struct Node* copyTail = copyHead;
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        //将复制节点解下来链接成一个新链表
        copyTail->next = copy;
        copyTail = copyTail->next;
        //恢复原链表的链接关系
        cur->next = next;
        //迭代往后走
        cur = next;
    }
    struct Node* result = copyHead->next;
    free(copyHead);//释放哨兵位头节点
    return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61

    在这里插入图片描述

    👉奇偶链表👈

    给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

    第一个节点的索引被认为是 奇数 ， 第二个节点的索引为偶数 ，以此类推。

    请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

    你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

    示例 1:

    在这里插入图片描述
    输入: head = [1,2,3,4,5]
    输出: [1,3,5,2,4]

    示例 2:

    在这里插入图片描述
    输入: head = [2,1,3,5,6,4,7]
    输出: [2,3,6,7,1,5,4]

    提示:

    • n == 链表中的节点数
    • 0 <= n <= 10^4
    • -10^6 <= Node.val <= 10^6

    思路：先将索引为奇数的节点链接成奇数链表，索引为偶数的节点链接成偶数链表，然后再将偶数链表的头链接到奇数链表的尾上，最后将 head 返回就行了。
    在这里插入图片描述

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* oddEvenList(struct ListNode* head)
{
    if(head == NULL)
        return head;
    struct ListNode* odd = head;
    struct ListNode* even = head->next;
    struct ListNode* evenHead = head->next;
    while(even && even->next)
    {
        //将奇数节点连起来
        odd->next = even->next;
        //迭代往后走
        odd = odd->next;
        //将偶数节点连起来
        even->next = odd->next;
        //迭代往后走
        even = even->next;
    }
    //奇数节点尾连着偶数节点的头
    odd->next = evenHead;
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    在这里插入图片描述

    👉二进制链表转整数👈

    给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

    请你返回该链表所表示数字的 十进制值 。

    示例 1：

    在这里插入图片描述
    输入：head = [1,0,1]
    输出：5
    解释：二进制数 (101) 转化为十进制数 (5)

    示例 2：

    输入：head = [0]
    输出：0

    思路：这道的主要考察的还是进制转换的知识，只不过是以链表的形式来考察。定义一个指针cur，cur指向头节点，当cur！=NULL时，执行ret = 2*ret+cur->val(二进制转十进制公式)。循环结束，将ret返回就行了。

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int getDecimalValue(struct ListNode* head)
{
    int ret = 0;
    struct ListNode* cur = head;
    while(cur)
    {
        ret = 2*ret + cur->val;
        cur = cur->next;
    }
    return ret;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    在这里插入图片描述

    👉删除链表的倒数第 N 个结点👈

    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

    示例 1：

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

    示例 2：

    输入：head = [1], n = 1
    输出：[]

    提示：

    • 链表中结点的数目为 sz
    • 1 <= sz <= 30
    • 0 <= Node.val <= 100
    • 1 <= n <= sz

    思路：先找出链表中的倒数第 N 个节点，然后将倒数第 N+1个节点和倒数第 N-1个节点链接起来，再将新的链表返回就行了。如何找到第 N-1个节点、第 N 个节点和第 N+1 个节点？先定义两个指针slow和fast，fast先走 N 步，然后slow和fast一起走，当fast==NULL时，slow就是倒数第 N 个节点，而slowPrev就是倒数第N+1个节点，slow->next就是倒数第 N-1 个节点。

    /**
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    struct ListNode* slowPrev = head;//倒数第N+1个节点
    //先找到倒数第N个节点，slow就是倒数第N个几点
    while(n--)
    {
        fast = fast->next;
    }
    while(fast)
    {
        slowPrev = slow;
        slow = slow->next;
        fast = fast->next;
    }
    //当slowPrev等于slow时，说明slow没有移动，要删除的节点是第一个节点
    if(slowPrev == slow)
    {
        head = head->next;
        return head;
    }
    //当slowPrev不等于slow时，说明slow移动了，要删除的节点不是第一个节点
    else
    {
        //将倒数第N+1个节点和倒数第N-1个节点链接起来
        slowPrev->next = slow->next;
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    在这里插入图片描述

    👉旋转链表👈

    给你一个链表的头节点 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 * 10^9

    思路：首先遍历一次链表，计算出链表的长度；然后让尾节点的next指向头节点，让链表成环；接着根据 k 的大小，更新头节点，尾节点指向NULL；最后将head返回就行了。
    在这里插入图片描述

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* rotateRight(struct ListNode* head, int k)
{
    if(head == NULL || k == 0)
        return head;
    int len = 1;
    struct ListNode* tail = head;
    while(tail->next)
    {
        //计算链表的长度
        len++;
        tail = tail->next;
    }
    //链接成环
    tail->next = head;
    //更新k的值
    k %= len;
    k = len-k;
    while(k--)
    {
        tail = tail->next;//tail走k步
    }
    //更新头节点
    head = tail->next;
    //尾节点指向NULL
    tail->next =NULL;
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    在这里插入图片描述

    👉删除排序链表中的重复元素👈

    给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回已排序的链表 。

    示例 1：

    在这里插入图片描述
    输入：head = [1,1,2]
    输出：[1,2]

    示例 2：

    在这里插入图片描述
    输入：head = [1,1,2,3,3]
    输出：[1,2,3]

    提示：

    • 链表中节点数目在范围 [0, 300] 内
    • -100 <= Node.val <= 100
    • 题目数据保证链表已经按升序排列

    思路：当节点cur的值和节点cur->next的值相等时，让cur->next = cur->next->next；当节点cur的值和节点cur->next的值不相等时，cur = cur->next。

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* deleteDuplicates(struct ListNode* head)
{
    if(head == NULL)
        return NULL;
    struct ListNode* cur = head;
    while(cur->next)
    {
        if(cur->val == cur->next->val)
            cur->next = cur->next->next;
        else
            cur = cur->next;
    }
    return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    在这里插入图片描述

    👉删除排序链表中的重复元素II👈

    给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。

    示例 1：

    在这里插入图片描述
    输入：head = [1,2,3,3,4,4,5]
    输出：[1,2,5]

    示例 2：

    在这里插入图片描述
    输入：head = [1,1,1,2,3]
    输出：[2,3]

    提示：

    • 链表中节点数目在范围 [0, 300] 内
    • -100 <= Node.val <= 100
    • 题目数据保证链表已经按升序 排列

    思路：因为要删除原始链表中所有重复数字的节点，只留下不同的数字，所以我们定义三个指针变量newHead、prev和cur。newHead是哨兵位头节点，不存储有效数据，方便头删；prev用于存储前一个节点的地址；cur用于访问节点的数据。当相邻节点的值相同时，利用while循环查找是否还有相同的值。当没有相同的值时，将prev->next赋值为cur，就将重复的值全部删除了。当相邻节点的值不相同时，直接执行cur = cur->next。

    在这里插入图片描述

    /*
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* deleteDuplicates(struct ListNode* head)
{
    //哨兵位头节点
    struct ListNode* newHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newHead->next = head;
    struct ListNode* cur = head;
    struct ListNode* prev = newHead;
    while(cur && cur->next)
    {
        //相邻节点的值相等
        if(cur->val == cur->next->val)
        {
            int val = cur->val;
            //找值不为val的节点
            while(cur && cur->val == val)
            {
                cur = cur->next;
            }
            prev->next = cur;
            //cur是值不为val的节点，让prev指向cur
        }
        //相邻节点的值不相等
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    struct ListNode* result = newHead->next;
    free(newHead);
    return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    在这里插入图片描述

    👉总结👈

    本篇博客讲解了七道链表OJ题，有简单题也有中等题，其中复制复杂链表最为重要，希望大家能够掌握。如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家啦！💖💝❣️

  • 相关阅读:
    图解LeetCode——面试题 01.08. 零矩阵（难度：中等）
    python中的运算符
    第二章 cadence后仿教程(Physical Verification).pdf
    OAuth2.0
    vue项目打包优化
    Split index API
    JavaScript之数组常用API
    当下社会和经济形势概述
    Mp4文件提取详细H.264和MP3文件
    图的几个基本概念：连通图、强连通图、完全图等
  • 原文地址：https://blog.csdn.net/m0_63639164/article/details/126463593