0
0

解剖—单链表相关OJ练习题

注：第六题和第七题牛客没有C环境，我在C++环境下用C语言写这道题（目前还没学C++，请大佬们理解一下，理解万岁！！）

一、移除链表元素

  1. 移除链表元素 - 力扣（LeetCode）
  • 给你一个链表的头节点 head 和一个整数 val
  • 请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

​

**输入：head = [1, 2, 6, 3, 4, 5, 6], val = 6
输出：[1, 2, 3, 4, 5]**

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* prev = NULL, * cur = head;
    while (cur) {        
        if (cur->val == val) {
            if (prev) {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
            else {
                cur = head->next;
                free(head);
                head = cur;
            }
        }
        else {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}

思路：链表常规删除，注意删除头节点的情况。

1、创建指向当前节点的前一个节点的指针prev=NULL（头节点的前一个节点为空），指针cur指向链表头节点。

2、以当前节点cur不为空为循环执行条件，判断当前节点的值是否等于val，等于则进行删除，不等于则prev更新为当前节点cur，当前节点cur指向下一个节点。

3、当前节点的值等于val时：

  • 如果值为 val 的节点不在头节点（prev 不为 NULL），将 prev 的 next 指针指向当前节点的下一个节点，然后释放当前节点并更新。
  • 如果值为 val 的节点在链表头节点（prev 为 NULL），则释放原来的头节点，将 head 更新为当前节点的下一个节点。

下面是第二种方法，创建新的链表，把不删除的节点链接到新链表 ：

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;        // 当前遍历节点
    struct ListNode* newhead = NULL;    // 新链表的头节点
    struct ListNode* tail = NULL;      // 新链表的尾节点

    while (cur) {
        if (cur->val != val) { // 当前节点的值不等于要删除的值
            if (tail == NULL) { // 第一次插入
                newhead = tail = cur; // 设置新链表的头和尾
            }
            else {
                tail->next = cur; // 将当前节点连接到新链表的尾部
                tail = tail->next; // 更新新链表的尾节点
            }
            cur = cur->next;     // 移动到下一个节点
            tail->next = NULL;  // 断开新链表的尾节点连接
        }
        else {
            struct ListNode* del = cur; // 保存需要删除的节点
            cur = cur->next;           // 移动到下一个节点
            free(del);                // 释放需要删除的节点的内存
        }
    }

    return newhead; // 返回新链表的头节点，已移除所有值为 val 的节点
}

二、找出链表的中间节点

  1. 链表的中间结点 - 力扣（LeetCode）
  • 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
  • 如果有两个中间结点，则返回第二个中间结点。

示例 1：

​

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

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

思路：快慢双指针

1、采用速度为1步的slow和速度为2步的fast，这样设置二者速度比较合理。

2、循环结束的条件需要考虑一下，分为链表节点个数为奇数和偶数，当fast走到最后的结果如下：

3、 所以循环结束的条件为 fast && fast->next 二者有一个为空。

三、合并两个有序链表

  1. 合并两个有序链表
  • 将两个升序链表合并为一个新的 升序 链表并返回。新
  • 链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

​

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

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
        return list2;
    if (list2 == NULL)
        return list1;

    struct ListNode* tail = NULL, * head = NULL;

    while (list1 && list2) {
        if (list1->val < list2->val) {
            if (tail == NULL) {
                head = tail = list1;
            }
            else {
                tail->next = list1;
                tail = tail->next;
            }
            list1 = list1->next;
        }

        else {
            if (tail == NULL) {
                head = tail = list2;
            }
            else {
                tail->next = list2;
                tail = tail->next;
            }
            list2 = list2->next;
        }
    }
    if (list1)
        tail->next = list1;
    if (list2)
        tail->next = list2;
    return head;
}

思路：创建新链表，较小的进行链接。

好像跟顺序表的题相像合并两个有序数组

不过，这次是单链表，所以我们可以创建新链表，从前向后将较小的链接到链表中，不需要从后先前了。

1、首先判断是否有链表为空，一个链表为空，则直接返回合并后的结果：另一个不为空的链表，都为空则返回任意一个链表。

2、创建新链表的尾节点tail和头节点head，初始化为空。

3、比较 list1 和 list2 当前节点的值。

  • 如果 list1 的当前节点值小于 list2 的当前节点值，将 list1 的节点添加到合并后的链表中。
  • 如果 list2 的当前节点值小于等于 list1 的当前节点值，将 list2 的节点添加到合并后的链表中。

4、在向合并链表中添加节点时，需要检查 tail 是否为 NULL，

  • 如果是，说明这是第一个节点，因此同时更新 head 和 tail。
  • 否则，只需将新节点连接到 tail 的 next 并将 tail 更新为新节点。

5、每次添加节点后，对应的链表list需要向后移动一位。

6、最终循环结束时，如果有链表不为空，证明该链表剩余节点的值均大于另一个链表的最大值，则将该链表其余的节点依次插入新链表。

7、返回新链表头节点head。

四、反转链表

  1. 反转链表

** 给你单链表的头节点 

head

，请你反转链表，并返回反转后的链表。**

示例 1：

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

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* rhead = NULL;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = rhead;
        rhead = cur;
        cur = next;
    }
    return rhead;
}

思路(一)： 创建新链表，从前向后取出原链表的节点进行头插。

  1. 开始时，定义两个指针 cur 和 rhead。
  • cur 指向原始链表的头部 head
  • rhead 用来构建反转后的链表，初始为空，表示反转后链表的尾部。
  1. 进入循环，这个循环将遍历整个链表并进行反转操作。循环的条件是 cur 不为 NULL，表示还有节点需要处理。
  1. 在循环内部，首先创建一个临时指针 next 来保存 cur 的下一个节点，因为在修改 cur->next 指针之前，需要先保存下一个节点的信息，否则会丢失对它的引用。
  1. 接着，将 cur->next 指向 rhead，这一步实际上是将 cur 的下一个节点指向反转后链表的头部，从而将 cur 从原链表中分离出来。
  1. 更新 rhead 为 cur，这一步将 cur 成为反转后链表的新头部。
  1. 更新 cur 为 next，这一步将 cur 移动到原链表中的下一个节点，准备处理下一个节点。
  1. 循环继续执行，直到 cur 变为 NULL，表示已经遍历完整个链表。此时，rhead 指向反转后链表的头部。
  1. 返回 rhead，它现在指向反转后的链表的头部，完成链表的反转。
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    struct ListNode* n1 = NULL;
    struct ListNode* n2 = head;
    struct ListNode* n3 = n2->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

** 思路(二)：调转链表方向（三指针）**

  • n1 初始化为 NULL，表示反转后的链表的尾部。
  • n2 初始化为链表的头部节点 head。
  • n3 初始化为 n2 的下一个节点，即 n2->next。

1、进入循环，这个循环将遍历整个链表并反转节点。

2、在循环内部，首先将 

n2

的 

next

指针指向 

n1

，这是为了将 

n2

的指针方向反转，将其指向前一个节点 

n1

，而不是原来的下一个节点。

3、接着更新 

n1

和 

n2

，将它们分别向前移动一个节点。

n1

移动到 

n2

的位置，

n2

移动到 

n3

的位置。

4、继续检查 

n3

是否为 NULL。如果 

n3

不为 NULL，将 

n3

移动到它的下一个节点，以便在下一轮循环中使用。

5、循环继续执行，直到 

n2

为 NULL，表示已经遍历完整个链表。此时，

n1

指向原链表的最后一个节点，它成为了反转后链表的头部。

6、返回 

n1

，它现在指向反转后的链表的头部，完成了链表的反转。

五、求链表中倒数第k个结点

链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com)

输入一个链表，输出该链表中倒数第k个结点。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow=pListHead,*fast=pListHead;
    int n=0;
    while(k){
        if(fast==NULL)
            return 0;
        fast=fast->next;
        k--;
    }

    while(fast){
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

思路： 快慢指针

快慢指针的速度都为1步，快指针先走k步，然后慢指针开始与快指针同时走，快指针走到最后为空时，慢指针则为倒数第k个节点。

1、通过while循环先让fast走k步，如果fast为空则无法求出倒数第k个节点（k大于链表长度）返回值为0。

2、第二个while循环slow和fast开始同时向后走，fast为空时，slow指向的节点即为所求倒数第k个节点。

六、链表分割

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

现有一链表的头指针 ListNode pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。*

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;

        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));

        struct ListNode* cur = pHead;
        while (cur) {
            if (cur->val < x) {
                lesstail->next = cur;
                lesstail = lesstail->next;
            }
            else {
                greatertail->next = cur;
                greatertail = greatertail->next;
            }
            cur = cur->next;
        }

        lesstail->next = greaterhead->next;
        greatertail->next = NULL;
        pHead = lesshead->next;

        free(lesshead);
        free(greaterhead);

        return pHead;
    }
};

** 思路：假设x=5，链表各节点值为**如下图：

1、创建变量* lesshead, * lesstail为小于x的链表的头节点和尾节点,

     * greaterhead, * greatertail 为大于x的链表的头节点和尾节点。

  • 为两个新链表头节点开辟空间，储存值val和指向下一个节点next。

2、在循环中判断cur的值是否小于x，小于则将cur链接到less链表，不小于则链接到grearter链表。

3、两个新链表需要链接合并成完整链表。

4、greatertail->next = NULL；

  • 这一步一定不能少，否则可以会出现循环链表：

七、链表的回文结构

链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

  • 1->2->2->1
  • 返回：true
class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head){
        struct ListNode* slow=head;
        struct ListNode* fast=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    struct ListNode* reverseList(struct ListNode* head){
        struct ListNode* cur=head,*rhead=NULL;
        while(cur){
            struct ListNode* next=cur->next;
            cur->next=rhead;
            rhead=cur;
            cur=next;
        }
        return rhead;
    }
    bool chkPalindrome(ListNode* head) {
        struct ListNode* mid=middleNode(head);
        struct ListNode* rmid=reverseList(mid);
        while(rmid){
            if(rmid->val==head->val){
                rmid=rmid->next;
                head=head->next;
            }
            else{
                return false;
            }
        }
        return true;
    }
};

思路：从中间点开始逆置，

八、判断链表是否相交

  1. 相交链表

给你两个单链表的头节点 

headA

和 

headB
  • 请你找出并返回两个单链表相交的节点。
  • 如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 

c1

开始相交：

​

  • 题目数据 保证 整个链式结构中不存在环。
  • 注意，函数返回结果后，链表必须 保持其原始结构 。
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++;
    }
    if(tailA!=tailB){
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode * longList=headA;
    struct ListNode * shortList=headB;
    if(lenA<lenB){
        longList=headB;
        shortList=headA;
    }
    while(gap--){
        longList=longList->next;
    }
    while(longList!=shortList){
        longList=longList->next;
        shortList=shortList->next;
    }
    return longList;
}

思路：长的链表走相差长度步数，然后短的开始和长的同时走，节点地址相等则相交。

1、定义变量 tailA 和 tailB 分别指向链表A和B的头节点，分别遍历对应链表获得链表长度lenA和lenB，因为while循环结束条件是tail->next为空，所以len的值初始化为1。

​

2、通过比较 

tailA

和 

tailB

是否相等来判断两个链表的尾节点是否一致。如果不相等，说明两个链表不可能有公共节点，直接返回 

NULL。

​

3、使用abs函数求出链表A与B长度差值，差值赋值给变量gap。

4、 创建两个指针longlist和shortlist分别指向链表A和B的头节点，然后判断链表大小，如果lenA大于lenB，则 longList=headB，否则 shortList=headA。

5、 longlist先向后走gap步，为了保持和shortlist同步遍历。

​

6、longlist和shortlist同时向后遍历，当二者相等时，停止遍历返回二者任意一个即为两个单链表相交的起始节点。

​

九、判断链表中是否有环(一)

  1. 环形链表

**给你一个链表的头节点 

head

，判断链表中是否有环。**

**注意：

pos

不作为参数进行传递 **。仅仅是为了标识链表的实际情况。

  • 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
  • 示例 1：​输入：head = [3,2,0,-4], pos = 1输出：true解释：链表中有一个环，其尾部连接到第二个节点。
bool hasCycle(struct ListNode *head) {
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast&&fast->next){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
            return true;
    }
    return false;
}

**思路：快慢指针 **

​

指针slow一次走一步，指针fast一次走两步，这样在链表中走，如果有环存在则二者一定会相遇，因为fast是slow速度的两倍。如果fast走到最后为空，证明该链表没有环存在。

当fast步数

十、 判断链表中是否有环(二)

  1. 环形链表 II

给定一个链表的头节点 

head
  • 返回链表开始入环的第一个节点。
  • 如果链表无环，则返回 null。
  • **不允许修改 **链表。
  • 示例 1：

​

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

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 (fast == slow) {
            struct ListNode* meet = slow;
            while (head != meet) {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}

思路：快慢指针

  • slow一次走一步，fast一次走两步，他们都从头节点head位置开始移动。
  • 设head到入环节点的距离为L，假设第一次相遇位置为meet，入环节点到meet的距离为X，相遇位置到入环节点的距离为环的周长C减去X。

​

  • slow走的路程：L+X
  • fast走的路程： L+X+n*C（slow进环前，fast走了n圈，比如：环很小则fast可能走了好几圈slow才进环）。
  • 因为fast的速度是slow的两倍，所以fast走的路程是slow的两倍，一圈之内fast一定追上slow！！
  • 由此可以得到以下关系式：2(L+X)=L+X+n*C
  • 化简得到：L=n*C-X 即 L=(n-1)C+C-X，
  • 这样就知道了 L=C-X，即一个指针从相遇点开始走，一个指针从头节点开始走，他们会在入环点相遇。
标签： 数据结构 c语言 链表
本文转载自: https://blog.csdn.net/m0_73800602/article/details/133906614
版权归原作者 Han同学 所有， 如有侵权，请联系我们删除。
登录后发布评论

“解剖—单链表相关OJ练习题”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航