网络知识 娱乐 【LeetCode】链表OJ题

【LeetCode】链表OJ题

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

目录

    • 👉复制带随机指针的链表👈
    • 👉奇偶链表👈
    • 👉二进制链表转整数👈
    • 👉删除链表的倒数第 N 个结点👈
    • 👉旋转链表👈
    • 👉删除排序链表中的重复元素👈
    • 👉删除排序链表中的重复元素II👈
    • 👉总结👈


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

给你一个长度为 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;
}

在这里插入图片描述

👉奇偶链表👈

给定单链表的头节点 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;
}

在这里插入图片描述

👉二进制链表转整数👈

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

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

示例 1:

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

示例 2:

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

思路:这道的主要考察的还是进制转换的知识,只不过是以链表的形式来考察。定义一个指针curcur指向头节点,当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;
}

在这里插入图片描述

👉删除链表的倒数第 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 个节点?先定义两个指针slowfastfast先走 N 步,然后slowfast一起走,当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;
    }
}

在这里插入图片描述

👉旋转链表👈

给你一个链表的头节点 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;
}

在这里插入图片描述

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

给定一个已排序的链表的头 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;
}

在这里插入图片描述

👉删除排序链表中的重复元素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
  • 题目数据保证链表已经按升序 排列

思路:因为要删除原始链表中所有重复数字的节点,只留下不同的数字,所以我们定义三个指针变量newHeadprevcurnewHead是哨兵位头节点,不存储有效数据,方便头删;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;
}

在这里插入图片描述

👉总结👈

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