目录

1.环形链表的约瑟夫问题

2.链表的中间节点

3.合并两个有序链表

4.反转链表

 5.移除链表元素

---

1.环形链表的约瑟夫问题

环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)

 

 思路：题目给出结构是环形链表，且题目已经定义好了环形链表的结构。

1.创建环形链表，对应数据为1~n。

2.定义一个变量i从1开始数，当i =m时就将该节点释放并重新连接链表。

3.直到单个节点成环时跳出循环，该节点的数据val即为幸存编号。 

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/#include <stdlib.h>
#include <stdio.h>
typedef struct ListNode ListNode;ListNode* BuyNode(int n)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->val = n;newnode->next = NULL;return newnode;
}ListNode* CreatList(int n)
{ListNode* phead = BuyNode(1);ListNode* ptail = phead;for(int i = 2; i <= n; i++){ListNode* newnode = BuyNode(i);ptail->next = newnode;ptail = ptail->next;}ptail->next = phead;return ptail;
}int ysf(int n, int m ) {// write code hereListNode* prev = CreatList(n);ListNode* pcur = prev->next;int i = 1;while(pcur->next != pcur){if(i == m){prev->next = pcur->next;free(pcur);pcur = prev->next;i = 1;}else{prev = pcur;pcur = pcur->next;i++;}}return pcur->val;
}

 需要注意的是当m=1是，最后一个人就是幸存者。

2.链表的中间节点

876. 链表的中间结点 - 力扣（LeetCode）

 思路：快慢指针法，快指针一次走一步，慢指针一次走两步。

当链表节点为奇数个时，循环结束标志是fast->next == NULL；

当链表节点为偶数个时，循环结束标志是fast == NULL；

要注意循环条件的前后顺序，&&会进行短路求值，如果写成（fast->next && fast）,当链表节点为偶数个时，此时fast == NULL，很明显NULL->next是错误的。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast = head;struct ListNode* slow = head;while(fast && fast->next)//注意这里短路，要注意顺序{fast = fast->next->next;slow = slow->next;}return slow;
}

3.合并两个有序链表

21. 合并两个有序链表 - 力扣（LeetCode）

 思路：创建一个新链表，给定两个指针遍历两条原链表，小的插入。当有剩余的链表时，直接将剩余的全部一起尾插到新链表中，无需一个一个尾插，因为原链表是有序的。

注意：会有一个原链表为空的情况，直接返回另一个原链表。

/*** 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* plist = NULL;ListNode* ptail = NULL;while(list1 && list2){if(list1->val < list2->val){if(plist == NULL){plist = ptail = list1;list1 = list1->next;}else{ptail->next = list1;ptail = ptail->next;list1 = list1->next;}}else{if(plist == NULL){plist = ptail = list2;list2 = list2->next;}else{ptail->next = list2;ptail = ptail->next;list2 = list2->next;}}}if(list1){ptail->next = list1;}if(list2){ptail->next = list2;}return plist;
}

4.反转链表

206. 反转链表 - 力扣（LeetCode）

 思路：创建新链表，一个一个头插，要注意连接顺序。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode; 
struct ListNode* reverseList(struct ListNode* head) {ListNode* plist = NULL;ListNode* pcur = head;while(pcur){if(plist == NULL){plist = head;pcur = pcur->next; plist->next = NULL;}else{ListNode* temp = pcur->next;pcur->next = plist;plist = pcur;pcur = temp;}}return plist;
}

 5.移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

 思路：创建一个新链表，newhead指向新链表的头节点，newtail指向当前链表的尾节点；

pcur遍历原链表，遇到val跳过，遇到非val链接到新链表。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* newhead = NULL;struct ListNode* newtail = NULL;struct ListNode* pcur = head;while(pcur){if(pcur->val != val){if(newhead == NULL){newhead = newtail = pcur;}else{newtail->next = pcur;newtail = pcur;}}pcur = pcur->next;}if(newtail){newtail->next = NULL;}return newhead;
}