【数据结构】链表力扣刷题详解

Table of Contents

前言

题目链接

移除链表元素

链表的中间结点

反转链表

分割链表

环形链表的约瑟夫问题

 

欢迎关注个人主页：逸狼

创造不易，可以点点赞吗~

如有错误，欢迎指出~

移除链表元素

题述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 

思路1：直接删除原链表中不符合的节点

遍历原链表，遇到val就执行删除操作
执行删除操作修改指针的指向有点麻烦，还有其他办法

思路2：满足要求的节点放在新链表上

定义新链表，利用pcur遍历原链表，找不为val的节点，尾插在新链表中
新链表：newHead  newTail

要考虑链表是否为空
链表为空：插入进来的节点就是链表的头节点和尾节点
链表不为空，插入进来的节点就是链表的新的尾节点

代码实现思路2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //定义新链表的头尾指针
    ListNode* newHead,* newTail;
    newHead=newTail=NULL;

    ListNode* pcur=head;
    while(pcur)
    {
        //不是val,尾插到新链表
        if(pcur->val!=val){
            //链表为空
            if(newHead==NULL)
            {
                newHead=newTail=pcur;
            }
            else{
                //链表不为空
                newTail->next=pcur;
                newTail=newTail->next;//
            }
        }
        //pcur继续往下走
        pcur=pcur->next;
    }
    if(newTail)//要先判断newTail本来是否为空
    {
        newTail->next=NULL;
    }
    return newHead;
}

链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点

思路1：统计链表中节点的个数，通过除2找到中间节点

for(统计链表个数）
    for(根据除2结果走到中间节点)

思路2：快慢指针

slow指针每次走1步，fast走2步
当fast->next或者fast走到为空，则slow刚好指向的就是中间节点
 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* fast,*slow;
    fast=slow=head;
    while(fast&&fast->next)//条件fast和fast->next不能相反，会造成短路
    {
        slow=slow->next;//slow走1步
        fast=fast->next->next;//fast走2步
    }
    return slow;
}

 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路1

创建新链表，遍历原链表的节点将其插入到新链表中

思路2：创建3个指针

分别记录前驱节点，当前节点，后继节点，改变原链表的指向1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //要先处理空链表
    if(head==NULL)
    {
        return head;
    }
    ListNode *n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=head->next;

    while(n2)
    {
        //修改n2的指向
        n2->next=n1;
        //n1,n2,n3往下走
        n1=n2;
        n2=n3;
        if(n3)//要先判断n3不为空，才能往下走
        {
            n3=n3->next;
        }
    }
    return n1;
}

合并两个有序链表

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

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

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, *l2;
    l1 = list1, l2 = list2;
    //创建头节点
    ListNode *newHead, *newTail;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));

    while (l1 && l2) {
        if (l1->val < l2->val) {
            // l1小，l1上，但要先判断l1不为空指针
            // if (newHead == NULL)
            //     newHead = newTail = l1;
            // else {
            //     newTail->next = l1;
            //     newTail = newTail->next;
            // }
            // l1 = l1->next;

            //代码优化
            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;

             //代码优化
            newTail->next=l2;
            newTail=newTail->next;
            l2=l2->next;
        }
    }
    if (l1) {
        newTail->next = l1;
    }
    if (l2) {
        newTail->next = l2;
    }
    return newHead->next;
}

分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你不需要 保留 每个分区中各节点的初始相对位置。

思路

定义2个链表：大链表和小链表，遍历原链表的节点将其放到对应的新链表中，最将大小链表首尾相连

创建大小链表都要先创建一个哨兵位

利用pcur遍历链表

代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

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;
    }
    //大链表尾要置为空
    greaterTail->next=NULL;

    //大小链表首尾相连
    lessTail->next=greaterHead->next;
    ListNode*ret=lessHead->next;
    free(greaterHead);
    free(lessHead);
    return ret;
}

环形链表的约瑟夫问题

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？、

代码实现

 //这道OJ题已经创建好了结构体结点，只是没有展示出来
 typedef struct ListNode ListNode;
//申请新节点
ListNode* BuyNode(int x)
{
    ListNode* newNode=(ListNode*)malloc(sizeof(ListNode));
    //可写可不写，一般不会申请失败
    if(newNode==NULL)
    {
        exit(1);
    }
    newNode->val=x;
    newNode->next=NULL;
    return newNode;
}
//创建循环链表
ListNode*createList(int n)
{
    //创建头节点
    ListNode* phead=BuyNode(1);
    ListNode* ptail=phead;
    //从2开始，共创建了n个节点
    for(int i=2;i<=n;i++)
    {
        ptail->next=BuyNode(i);
        ptail=ptail->next;
    }
    //链表要首尾相连，循环起来
    ptail->next=phead;
    return phead;
}
int ysf(int n, int m ) {
    //创建不带头单向循环链表
    //逢m删除节点
    ListNode*head=createList(n);
    ListNode*pcur=head;
    ListNode*prev=NULL;//用于记录pcur走过的位置,是pcur的前驱节点

    int count=1;
    //逢m删除节点
    while(pcur->next!=pcur)//表示删除节点到只剩下自己跳出循环
    {
        if(count==m)
        {
            //删除当前节点pcur
            prev->next=pcur->next;
            free(pcur);
            //删除pcur节点后，要让pcur走到新的位置，count置为初始值
            pcur=prev->next;
            count=1;
        }
        else 
        {
            //pcur往后走
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    //此时pcur节点就是幸存下来的节点
    return pcur->val;
}