阅读量:4
前言
题目链接
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
移除链表元素
题述
给你一个链表的头节点 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; }