【数据结构】单链表OJ题

前言:
本节博客将讲解单链表的反转，合并有序链表，寻找中间节点及约瑟夫问题

文章目录

一、反转链表

要反转链表，我们需要遍历链表并改变每个节点的 next 指针，使其指向其前一个节点。为了完成这个任务，我们需要三个指针：prev、cur和 next_node。

• prev：保存当前节点的前一个节点。初始化为 NULL，因为链表的新头部（原始链表的尾部）的 next 指针将指向 NULL。
• cur：表示当前正在处理的节点。
• next_node：保存当前节点的下一个节点。

structListNode*reverseList(structListNode* head){typedefstructListNode ListNode;
    ListNode* prev =NULL;
    ListNode* cur = head;
    ListNode* next_node =NULL;while(cur !=NULL){
        next_node = cur->next;// 保存当前节点的下一个节点
        cur->next = prev;// 更新当前节点的next指针
        prev = cur;// 将prev移动到当前节点
        cur = next_node;// 移动到下一个节点}return prev;// 返回新的头部}

二、合并有序链表

分为四个步骤：

• 开始阶段: 首先，函数检查两个列表是否为空。如果其中一个为空，则直接返回另一个列表，因为没有合并的必要。
• 初始化合并链表的头: 函数接着检查list1和list2的首个节点，看哪一个的值较小。较小的那个节点将成为新的合并链表的首个节点。
• 合并过程: 使用一个while循环来遍历list1和list2，每次循环会从这两个列表中选择一个较小的节点，并将其添加到合并列表的末尾。
• 处理剩余节点: 循环结束后，list1和list2可能还有未处理的节点。以下的代码将剩余的节点添加到合并列表的末尾。

typedefstructListNode ListNode;structListNode*mergeTwoLists(structListNode* list1,structListNode* list2){//开始阶段if(!list1)return list2;if(!list2)return list1;//初始化合并链表的头
    ListNode* mergedHead =NULL;// 合并后的链表头if(list1->val < list2->val){
        mergedHead = list1;
        list1 = list1->next;}else{
        mergedHead = list2;
        list2 = list2->next;}

    ListNode* cur = mergedHead;// 指向合并后链表的当前节点//合并过程while(list1 && list2){if(list1->val <= list2->val){
            cur->next = list1;
            list1 = list1->next;}else{
            cur->next = list2;
            list2 = list2->next;}
        cur = cur->next;}//处理剩余节点// 如果list1还有剩余节点if(list1){
        cur->next = list1;}// 如果list2还有剩余节点if(list2){
        cur->next = list2;}return mergedHead;}

三、链表的中间结点

这题我们可以使用快慢指针，在循环中，fast 指针每次移动两个节点，而 slow 指针每次只移动一个节点。这意味着，当 fast 指针到达链表的末尾时，slow 指针将位于链表的中间位置。

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

四、环形链表的约瑟夫问题

以下是代码的主要思路：

1. 数据结构选择： 使用单向循环链表来模拟这个问题。循环链表是一个适合此问题的数据结构，因为当链表到达末尾时，它可以自动回到头部。
2. 链表节点创建： ListBuyNode(int x)：这个函数用于创建一个新的链表节点，它接受一个整数值 x 作为参数，并返回一个新的链表节点。
3. 循环链表创建： CreateList(int n)：这个函数用于创建一个有 n 个节点的单向循环链表。链表的节点值从 1 到 n。链表的最后一个节点指向头节点，使其形成一个循环。
4. 约瑟夫环算法：

• ysf(int n, int m)：这个函数实现了约瑟夫环的主要算法。
• 首先，它调用 CreateList(n) 来创建一个 n 个节点的单向循环链表。
• 使用两个指针，prev 和 cur，分别表示当前节点的前一个节点和当前节点。
• 使用一个计数器 count 从 1 开始计数，每次循环增加计数器的值。
• 当 count 达到 m 时，当前的 cur 节点将被删除（淘汰），并释放其内存。然后，cur 指向下一个节点，并且计数器重置为 1。
• 如果 count 不等于 m，prev 和 cur 都向前移动一个节点，继续循环。
• 当链表只剩下一个节点时（即 cur->next 等于 cur 时），循环结束。
• 返回最后一个剩下的节点的值，即最后一个被淘汰的人的位置。

// 定义链表节点结构typedefstructListNode ListNode;// 分配内存并创建一个链表节点，值为x
ListNode*ListBuyNode(int x){
    ListNode* node =(ListNode*)malloc(sizeof(ListNode));// 分配内存if(node ==NULL){// 检查内存分配是否成功perror("Malloc fail;");exit(1);// 分配失败，退出程序}
    node->val = x;// 设置节点的值
    node->next =NULL;// 初始化下一个节点为NULLreturn node;// 返回创建的节点}// 创建一个包含n个节点的单向循环链表
ListNode*CreateList(int n){
    ListNode* phead =ListBuyNode(1);// 创建头节点，值为1
    ListNode* pTail = phead;// 初始化尾节点为头节点for(int i =2; i <= n; i++){// 从2到n循环创建节点
        ListNode* node =ListBuyNode(i);// 创建新节点
        pTail->next = node;// 把新节点连接到链表的尾部
        pTail = pTail->next;// 更新尾节点为新创建的节点}
    pTail->next = phead;// 将链表的尾部连接到头部，使其成为一个循环链表return pTail;// 返回链表的尾节点}// 约瑟夫环问题的解决函数intysf(int n,int m ){
    ListNode* prev =CreateList(n);// 创建一个单向循环链表，并返回尾节点
    ListNode* cur = prev->next;// 当前节点从头节点开始int count =1;// 计数器初始化为1while(cur->next != cur){// 当链表只剩下一个节点时停止循环if(count == m){// 当计数器达到m时
            prev->next = cur->next;// 删除当前节点free(cur);// 释放当前节点的内存
            cur = prev->next;// 更新当前节点为下一个节点
            count =1;// 重置计数器}else{
            prev = cur;// 否则，移动到下一个节点
            cur = cur->next;
            count++;// 增加计数器}}return cur->val;// 返回最后剩下的节点的值}

如果你喜欢这篇文章，点赞👍+评论+关注⭐️哦！
欢迎大家提出疑问，以及不同的见解。