前言
题目链接
移除链表元素
链表的中间结点
反转链表
分割链表
环形链表的约瑟夫问题
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
移除链表元素
题述
给你一个链表的头节点 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){//删除当前节点pcurprev->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;
}
