前言

题目链接

移除链表元素

链表的中间结点

反转链表

分割链表

环形链表的约瑟夫问题

 

​

欢迎关注个人主页：逸狼

---

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

如有错误，欢迎指出~

移除链表元素

题述

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