数据结构——经典链表OJ（二）

乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen
我的专栏：c语言
点击主页：optimistic_chen和专栏：c语言，
创作不易，大佬们点赞鼓励下吧~

文章目录

合并两个有序链表
- 第一种思路
- 第二种思路
环形链表的约瑟夫问题
分割链表
- 第一种思路
- 第二种思路
完结

合并两个有序链表

合并两个有序链表———力扣
在这里插入图片描述

第一种思路

直接创建一个空链表，分别判断两个原链表的元素大小，升序插入到新链表中，但是此方法可能会超出时间限制（每一次都需要判断新链表的头节点是否为空），代码重复执行太多。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //判断为空链表
    if(list1==NULL){
        return list2;
    }
    if(list2==NULL){
        return list1;
    }

    ListNode* l1=list1;
    ListNode*l2=list2;

    //创建的新链表
    ListNode*newHead,*newTail;
    newHead=newTail=NULL;

    while(l1&&l2)
    {
        if(l1->val < l2->val)
        {
            //l1拿下来尾插
            if(newHead==NULL){
                newHead=newTail=l2;
                }
                else{
                    newTail->next=l1;
                    newTail=newTail->next;
                }
            
            l1=l1->next;
        }
        else
        {
            //l2拿下来尾插
            if(newHead==NULL){
            newHead=newTail=l2;
            }
            else{
                newTail->next=l2;
                newTail=newTail->next;
            }
            l2=l2->next;
        }

    }
    //跳出循环，要么l1先为空，要么l2先为空
    if(l2)
    {
        newTail->next=l2;
    }
    if(l1)
    {
        newTail->next=l1;
    }
    return newHead;
}

第二种思路

优化：让新链表不为空，判断两个原链表元素大小后，直接插入到新链表中

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //判断为空链表
    if(list1==NULL){
        return list2;
    }
    if(list2==NULL){
        return list1;
    }

    ListNode* l1=list1;
    ListNode*l2=list2;

    //创建的新链表(链表不为空)
    ListNode*newHead,*newTail;
    //newHead=newTail=NULL;
    newHead=newTail=(ListNode*)malloc(sizeof(ListNode));

    while(l1&&l2)
    {
        if(l1->val < l2->val)
        {
            //l1拿下来尾插
            newTail->next=l1;
            newTail=newTail->next;
            l1=l1->next;
        }
        else
        {
            //l2拿下来尾插
            newTail->next=l2;
            newTail=newTail->next;
            l2=l2->next;
        }

    }
    //跳出循环，要么l1先为空，要么l2先为空
    if(l2)
    {
        newTail->next=l2;
    }
    if(l1)
    {
        newTail->next=l1;
    }

    //动态申请的空间要手动释放掉
    ListNode* ret=newHead->next;
    free(newHead);
    newHead=NULL;
    return ret;
}

环形链表的约瑟夫问题

环形链表的约瑟夫问题——牛客网
在这里插入图片描述
环形链表与我们平时见到的链表不同的是：他的尾节点的next指针指向头节点，而不是NULL。

在这里插入图片描述

typedef struct ListNode ListNode;
 //创建节点
 ListNode*buyNode(int x)
 {
    ListNode*node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL)
    {
        exit(1);
    }
    node->val=x;
    node->next=NULL;
    return node;
 }
 ListNode*createCircle(int n)
 {
    //先创建第一个节点
    ListNode*phead=buyNode(1);
    ListNode*ptail=phead;
    for(int i=2;i<=n;i++)
    {
        ptail->next=buyNode(i);
        ptail=ptail->next;
    }
    //首位相连
    ptail->next=phead;
    return ptail;
 } 
int ysf(int n, int m ) {
    //第一步，根据n创建带环链表
    ListNode*prev=createCircle(n);
    ListNode*pcur=prev->next;
    //第二步记数
    int count=1;
    while(pcur->next!=pcur)
    {
        if(count==m)
        {
            //销毁pcur节点
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
        else 
        {
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    //此时剩下的一个节点就是要返回的值
    return pcur->val;

}

分割链表

分割链表——力扣
在这里插入图片描述

第一种思路

双指针法：
1.创建大，小两个新链表。
2.将小于特定值的节点放到小链表中，将大于等于特定值的节点放到大链表中
3.小链表的尾节点和大链表的第一个有效节点首尾相连

在这里插入图片描述

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head==NULL)
    {
        return head;
    }
    //创建两个带头链表
    ListNode*lessHead,*lessTail;
    ListNode*greaterHead,*greaterTail;
    lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));
    greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));
    
    //遍历原链表，将原链表中的节点尾插到大小链表中
    ListNode*pcur=head;
    while(pcur)
    {
        if(pcur->val<x)
        {
            //尾插到小链表中
            lessTail->next=pcur;
            lessTail=lessTail->next;
        }
        else
        {
            //尾插到大链表中
            greaterTail->next=pcur;
            greaterTail=greaterTail->next;
        }
        pcur=pcur->next;
    }
    //修改大链表的尾节点的next指针指向
    greaterTail->next=NULL;
    //小链表的尾节点和大链表的第一个有效节点首尾相连
    lessTail->next=greaterHead->next;

    ListNode*ret=lessHead->next;
    free(lessHead);
    free(greaterHead);
    lessHead=greaterHead=NULL;
    return ret;
}

第二种思路

HeadNode哨兵结点：用于头插；Tail尾指针用于尾插；cur表示当前链表结点；
遍历链表依次用链表结点元素值与X比较；小于则头插；大于则尾插；
这里有一个小细节就是头插时，如果尾指针等于哨兵HeadNode则需更新Tail指向尾结点

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* HeadNode=(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* Tail=HeadNode,*cur=head;
    Tail->next=NULL;
    while(cur){
        struct ListNode* next=cur->next;
        if(cur->val<x){
            cur->next=HeadNode->next;
            HeadNode->next=cur;
            if(Tail==HeadNode){
                Tail=cur;
            }
        }else{
            Tail->next=cur;
            Tail=cur;
            cur->next=NULL;
        }
        cur=next;
    }
    return HeadNode->next;
}