一、移除链表元素

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

(列表中的节点数目在范围 [0, 104] 内)

示例：输入：head = [1,2,6,3,4,5,6], val = 6          输出：[1,2,3,4,5]

          输入：head = [ ], val = 1                              输出：[ ] 

          输入：head = [7,7,7,7], val = 7                    输出：[ ]

思路1：创建一个新链表，遍历找值不为val的节点，尾插到新的链表中

需要创建一个指针pcur，让它从phead开始寻找不为val的节点，将它们尾插在新的链表中，至于等于val的节点就跳过它；除此之外，我们还需要创建一个新链表，用两个指针newHead,newTail来保存新的头节点和尾节点，开始时先将它们置为NULL。

但是需要注意：根据题目给的链表内节点数目的范围，可知链表有为空的情况，需要判空，如果原链表为空，意味着原链表内没有任何节点，那么就不需要再进行遍历循环，直接跳出了函数，返回一个空的新链表

//移除链表元素函数
SLNode* removeElements(SLNode* phead,int val)
{//创建新链表SLNode* newHead = NULL;SLNode* newTail = NULL;//遍历原链表SLNode* pcur = phead;while(pcur){//找到不为val的节点，尾插到新链表中if(pcur->val != val){//链表为空if(newHead == NULL){newHead = newTail = pcur;}else{//链表不为空newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if(newTail) //当原链表为空时，不需要进行置空操作newTail->next = NULL;//返回新的头节点return newHead;
}
//创建单链表节点结构
typedef struct SListNode
{int val;struct SListNode* next;
}SLNode;
//创建新节点
SLNode* newnode(int x)
{SLNode* node = (SLNode*)malloc(sizeof(SLNode));if(node == NULL){perror("malloc");exit(1);}node->val = x;node->next = NULL;return node;
}
//打印链表
void Print(SLNode* phead)
{SLNode* pcur = phead;while(pcur){printf("%d ",pcur->val);pcur = pcur->next;}printf("\n");
}
int main()
{//创建测试链表：1->2->6->3->4->5->6SLNode* phead = newnode(1);phead->next = newnode(2);phead->next->next = newnode(6);phead->next->next->next = newnode(3);phead->next->next->next->next = newnode(4);phead->next->next->next->next->next = newnode(5);phead->next->next->next->next->next->next = newnode(6);printf("原始链表:");Print(phead);int val = 6;SLNode* result = removeElements(phead,val);printf("移除%d后的新链表:"，val);Print(result);//释放链表内存while(result){SLNode* tmp = result;result = result->next;free(tmp);tmp = NULL;}return 0;
}

测试原链表为空时：

SLNode* phead = NULL;

测试原链表元素相同时：

SLNode* phead = newnode(7);
phead->next = newnode(7);
phead->next->next = newnode(7);
phead->next->next->next = newnode(7);int val = 7;

思路2：遍历原链表，将值为val的节点释放

使用 prev,pcur,next三指针法：pcur表示当前的节点，prev表示当前节点的前一个节点，next表示当前节点的下一个节点；将pcur节点释放掉之前，需要改变prev的next节点变为next，才能将其释放掉，初始时将prev和next置为NULL

SLNode* removeElements(SLNode* phead,int val)
{SLNode* prev = NULL;//前一个节点指针SLNode* pcur = phead;//当前节点指针SLNode* next = NULL;//下一个节点指针while(pcur){next = pcur->next;//保存下一个节点if(pcur->val == val){//删除当前节点if(prev == NULL){//删除的是头节点phead = next;//更新头指针}else{//删除的是中间或尾节点prev->next = next;//释放当前节点内存free(pcur);pcur = NULL;}}else{//当前节点保留，更新prev指针prev = pcur;}//移动到下一个节点pcur = next;}return phead;
}

二、反转链表

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

(链表中节点的数目范是 [0, 5000])

示例： 输入：head = [1,2,3,4,5]      输出：[5,4,3,2,1]

            输入：head = [1,2]               输出：[2,1]

            输入：head = [ ]                    输出：[ ]

思路1：创建新链表，将原链表中的节点拿过来头插

用两个指针newHead,newTail来保存新链表的头节点和尾节点，每头插一个节点newHead就跟着变化，变成新的头节点

根据题目节点的数目范围可知，链表有可能为空链表，因此需要判空。

SLNode* reverseList(SLNode* phead)
{//创建一个空链表SLNode* newHead = NULL;SLNode* newnode = NULL;//遍历原链表SLNode* pcur = phead;while(pcur){//1.保存下一个节点（防止丢失）SLNode* next = pcur->next;if(newHead == NULL){newHead = newTail = pcur;pcur->next = NULL;}else{//2.将当前节点插入新链表头部pcur->next = newHead;//当前节点指向新链表的第一个节点newHead = pcur;//更新新链表头指针}//3.移动到原链表的下一个节点pcur = next;}return newHead; //如果元链表为空，直接会返回NULL
}

如果新链表只给一个指针newHead来维护：

SLNode* reverseList(ListNode* phead)
{//创建新链表SLNode* newHead = NULL;//遍历链表SLNode* pcur = phead;    while(pcur){//1.保存下一个节点（防止丢失）SLNode* next = pcur->next;//2.将当前节点插入新链表头部pcur->next = newHead;newHead = pcur;//3.移动到原链表的下一个节点pcur = next;}return newHead;
}

思路2：创建三个指针，完成原链表的反转

创建三个指针n1,n2,n3，分别表示当前节点的前一个节点，当前节点，当前节点的后一个节点，开始时n1置为NULL。具体做法：(1)让n2的next指针指向n1

                                                  (2)然后n1=n2; n2=n3; n3=n3->next

SLNode* reverseList(ListNode* phead)
{//判空if(phead == NULL){return NULL;}//创建三个指针SLNode* n1,n2,n3;n1 = NULL,n2 = phead, n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}//指向新的头节点n1return n1;
}

三、链表的中间节点

给你单链表的头结点 phead ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

（链表的结点数范围是 [1, 100]）

示例：输入：head = [1,2,3,4,5]    输出：[3,4,5] （链表只有一个中间结点，值为 3）

输入：head = [1,2,3,4,5,6]  输出：[4,5,6] （该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点）

思路1：遍历原链表，使用count变量计数，直接返回 count/2 节点

例如，当有奇数个节点时，5个节点，则 5/2=2，2即中间节点

           当有偶数个节点时，6个节点，则 6/2=3，3即中间节点

SLNode* middleNode(SLNode* phead)
{if(phead == NULL){return NULL; //空链表直接返回}//第一次遍历：计算链表长度int count = 0;SLNode* pcur =phead;while(pcur){count++;pcur = pcur->next;}//计算中间位置int mid = count/2;//第二次遍历：移动到中间节点pcur = phead;if(int i = 0;i < mid; i++){pcur = pcur->next;}return pcur;
}

测试奇数个节点时：

测试偶数个节点时：

测试只有一个节点和空链表时：

思路2：快慢指针

slow每次走一步，fast每次走两步，

例如，当有奇数个节点时，5个节点，slow走一步，fast走两步，到最后一个节点时，fast->next 刚好等于NULL(fast->next == NULL)，slow指向的刚好是中间节点；

当有偶数个节点时，6个节点，slow走一步，fast走两步，到最后一个节点时，fast刚好等于NULL(fast == NULL),slow指向的刚好是中间节点

SLNode* middleNode(SLNode* phead)
{if(phead == NULL){return NULL;}//创建快慢指针SLNode* slow = phead;SLNode* fast = phead;//快指针每次移动两步，慢指针每次移动一步while(fast && fast->next) //不可以反过来写成 (fast->next && fast),因为如果链表中有偶数个节点的情况下，fast最后一次会直接走空 NULL，{                         //fast->next执行会报错slow = slow->next;    fast = fast->next->next;}//此时slow刚好指向的就是中间节点return slow;
}

四、合并两个有序链表

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

（两个链表的节点数目范围是 [0, 50]，

 l1 和 l2 均按 非递减顺序 排列）

示例：输入：l1 = [1,2,4] , l2 = [1,3,4]       输出：[1,1,2,3,4,4]

           输入：l1 = [ ], l2 = [ ]                      输出：[ ]

           输入：l1 = [ ] , l2 = [0]                     输出：[0]

思路：创建一个空链表，遍历原链表，将节点值小的节点拿到新的链表中进行尾插操作

需要创建两个指针l1,l2，分别遍历两个原链表，还要创建一个新的链表，同时维护新链表的头指针(newHead)和尾指针(newTail)

和前面我们做的顺序表的 合并两个有序数组 算法题一样，结果只有两种情况：要么l1为空，要么l2为空

SLNode* mergeTwoLists(SLNode* list1,SLNode* list2)
{//判空if(list1 == NULL){return list2;//如果两个链表都为空，则会返回空链表[ ]}if(list2){return list1;}SLNode* l1 = list1;SLNode* l1 = list2;//创建新链表SLNode* newHead,newTail;newHead = newTail = NULL;while(l1 && l2){if(l1->val < l2->val){//l1拿下来尾插if(newHead == NULL){newHead = newTail = l1;}else{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;}}//跳出循环有两种情况：要么l1走到空，要么l2走到空if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}return newHead;
}

测试空链表时：

测试有一个链表为空一个不为空时：

添加哨兵位节点优化代码

在上面的代码中，存在重复的代码(如下图所示)，如何优化？

重复的原因：新链表存在空链表和非空链表两种情况，解决思路：让新链表不为空--头尾指针都指向一个有效的地址（节点），即使用带头链表（哨兵位节点）

将较小的节点一个个尾插到新链表的哨兵节点后面，遍历完成之后返回的是链表的第一个有效节点

（哨兵节点详情：数据结构-单链表-CSDN博客）

SLNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{//判空if (list1 == NULL){return list2;// [ ]如果两个链表都为空，则会返回空链表}if (list2 == NULL){return list1;}SLNode* l1 = list1;SLNode* l2 = list2;//创建新的链表SLNode* newHead,*newTail;//创建哨兵节点newHead = newTail = (SLNode*)malloc(sizeof(SLNode));while(l1 && l2){if(l1->val <l2->val){newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}//动态申请的空间手动释放掉SLNode* ret = newHead->next; //返回的是第一个有效节点free(newHead);newHead = NULL;return ret;
}

五、循环链表经典应用-环形链表的约瑟夫问题

【背景：著名的Josephus问题

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与 Josephus及他的朋友躲到⼀个洞中，39个犹太人决定宁愿死也不要被⼈抓到，于是决定了⼀个自杀方式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须自杀，然后再由下⼀ 个重新报数，直到所有⼈都自杀身亡为止。 然⽽Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在 第16个与第31个位置，于是逃过了这场死亡游戏。】

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

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

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

示例：输入：5，2          输出：3

说明：

开始5个人 1，2，3，4，5 ，从1开始报数，1->1，2->2编号为2的人离开

1，3，4，5，从3开始报数，3->1，4->2编号为4的人离开

1，3，5，从5开始报数，5->1，1->2编号为1的人离开

3，5，从3开始报数，3->1，5->2编号为5的人离开

最后留下人的编号是3

思路：第一步：创建带环链表 第二步：计数

我们通过题意可知，是一个环形的，循环的链表，依然可以用双指针法解决，创建两个指针pcur,prev，pcur代表当前链表的节点，prev表示该节点的前一个节点，根据示例，一共有5个人，报数报到2的人要离开；prev开始的位置是在最后一个人即5的位置，pcur开始的位置就是1，走到下一步的时候就是2，是需要删除（离开）的节点，删除方式：pcur走到2时，此时的prev也要跟着走一步，到1的位置，改变prev的next指针的指向位置，即由 prev->next=pcur变成prev->next=pcur->next,然后就可以删除pcur位置的节点；接着，此时pcur由删除的节点位置继续往下走，走向下一个有效的节点继续从1开始报数，然后重复上述的操作

SLNode* creatCircle(int n)
{//先创建第一个节点SLNode* phead = newnode(1);SLNpde* ptail = phead;for(int i = 0;i <= n; i++){ptail->next = newnode(i);ptail = ptail->next;}//首尾相连，链表成环ptail->next = phead;return ptail;
}
int ysf(int n,int m)
{//1.根据n创建带环链表SLNode* prev = creatCircle(n);SLNode* pcur = prev->next;int count = 1;//当链表中只有一个节点的情况 pcur->next == pcur,这个节点的数据就是留到最后的人while(pcur->next != pcur){if(count == m){//销毁pcur节点prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;}else{//此时不需要销毁节点prev = pcur;pcur = pcur->next;count++;}}//此时剩下的一个节点就是要返回的节点里的值int ret = pcur->val;free(pcur);pcur = NULL:return ret;
}

六、分割链表

给你一个链表的头节点 phead 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

(链表中节点的数目在范围 [0, 200] 内)

示例：输入：head = [1,4,3,2,5,2], x = 3          输出：[1,2,2,4,3,5]

           输入：head = [2,1], x = 2                      输出：[1,2]

思路1：创建两个新链表--小链表和大链表

将原链表中小于x的pcur节点的值尾插到小链表中，同时维护小链表的头指针(lessHead)和尾指针(lessTail)

将原链表中大于或等于x的pcur节点的值尾插到大链表中，同时维护大链表的头指针(greaterHead)和尾指针(greaterTail),最后将小链表的尾节点与大链表的第一个有效节点首尾相连

SLNode* partition(SLNode* phead,int x)
{//判空if(phead == NULL){return phead;}//创建两个带头链表SLNode* lessHead,*lessTail;SLNode* greaterHead,*greaterTail;lessHead = lessTail = (SLNode*)malloc(sizeof(SLNode));greaterHead = greaterTail = (SLNode*)malloc(sizeof(SLNode));//遍历原链表，将原链表中的节点尾插到大小链表中SLNode* pcur = phead;while(pcur){if(pcur->val < x){//尾插到小链表中lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大链表中greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//修改大链表的尾节点的next指针指向(终止大链表)greaterTail->next = NULL;//若不加这一行，代码会出现死循环+next指针初始化//小链表的尾节点和大链表的第一个有效节点首尾相连lessTail->next = greaterHead->next;//释放SLNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;
}

测试空链表：

测试只有小于x或大于等于x的情况：

思路2：创建一个新链表

将原链表中若pcur节点的值小于x，头插到新链表中，若pcur节点的值大于或等于x，尾插到新链表中，同时维护新链表的头指针(newHead)和尾指针(newTail)，给新链表一个哨兵节点

SLNode* partition(SLNode* phead,int x)
{if(phead == NULL){return NULL;}//创建一个带头链表//创建哨兵节点作为新链表的头SLNode* newHead,*newTail;newHead = newTail = (SLNode*)malloc(sizeof(SLNode));newHead->next = NULL;    SLNode* pcur = phead;while(pcur){//保存下一个节点SLNode* next = pcur->next;//在头插操作时，pcur 的 next 会被修改if(pcur->val < x){//头插到哨兵节点后面//要在哨兵节点newHead后面进行头插，即在newHead->next节点位置开始进行头插，而这个位置原本为NULL，即newHead,newHead->next=NULL=NULL//现在要变成 newHead,pcur,newHead->next=NULL,在NULL前面插入pcur，那么pcur->next就变成了NULL（pcur->next = newHead->next;）//哨兵节点的next节点就变成了pcur（newHead->next = pcur; ）pcur->next = newHead->next;newHead->next = pcur;//如果是第一个节点，需要更新newTailif(newTail == newHead){newTail = pcur;}}else{//尾插到链表末尾newTail->next = pcur;newTail = pcur;//newTail = newTail->next 更新尾指针 }pcur = next;}newTail->next = NULL;// 确保链表终止//释放SLNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}

思路3：遍历原链表，在原链表上进行修改

若pcur节点的值小于x，往后走，若pcur节点的值大于或等于x，尾插到原链表后，删除旧节点

我们需要一个指针pcur，表示当前的节点，prev指针则表示当前节点的前一个节点（设置prev开始时的位置在哨兵节点上），pcur每走一步，prev就保存pcur前一步的位置，还需要一个ptail指针表示原链表的尾节点（ptail一直保持位置不变，表示原尾节点位置），一个newTail指针表示随着每次尾插的变化的新的尾节点

当走到大于或等于x的节点位置时，修改prev的next指针的位置，即prev->next=pcur变成prev->next=pcur->next，然后将pcur节点尾插到原链表后面，newTail跟着移动，将旧的pcur节点删除掉，再接着继续往后走，重复以上的操作。

SLNode* partition(SLTNode* phead, int x)
{if(phead == NULL || phead->next == NULL) //链表为空或链表只有一个节点{return phead;}//1.找到原链表的尾节点SLNode* ptail = phead;while(ptail->next){ptail = ptail->next;}SLNode* newTail = ptail;//新的尾节点指针    //2.创建哨兵节点简化操作SLNode* newHead = (SLNode*)malloc(sizeof(SLNode));newHead->next = phead;SLNode* prev = newHead;//前驱指针SLNode* pcur = phead;//当前指针//3.遍历链表直到原始尾节点while(pcur != ptail){if(pcur->val < x){//保留当前节点，继续前进prev = pcur;pcur = pcur->next;}else{//将当前节点移到链表末尾//从原位置移除当前节点prev->next = pcur->next;//将当前节点插入到末尾newTail->next = pcur;pcur->next = NULL;newTail = pcur;//更新新的尾节点//移动pcur到prev的下一个节点pcur = prev->next;//相当于pcur=pcur->next,但是不能这么写，因为此时pcur->next 已经被设为 NULL，会导致错误}}//4.处理原始尾节点if(ptail->val >= x && ptail != newTail)//如果ptail已经是newTail（即已经被移动过一次），这个条件ptail != newTail可以防止重复移动{//如果原始尾节点需要移动prev->next = ptail->next;//实际上ptail->next是NULL,因为ptail是原始链表的尾节点，它的next本来就是NULLnewTail->next = ptail;ptail->next = NULL;newTail = ptail;}//5.释放哨兵节点并返回结果SLNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}

其实不用处理尾节点也可以，因为到了尾节点的部分要么前面的节点包括尾节点本身都是小于x的，不用移动保持原样，要么尾节点是大于等于x的，就尾插到当前链表的末尾

关键说明：为什么可以不需要单独处理尾节点

1. 当原始尾节点小于 x 时：

   • 当 pcur 指向原始尾节点时，进入 if 分支

   • 执行 prev = pcur 和 pcur = pcur->next

   • 由于原始尾节点的 next 是 NULL，pcur 变为 NULL

   • 循环条件 while(pcur != NULL) 不满足，循环结束

2. 当原始尾节点大于等于 x 时：

   • 当 pcur 指向原始尾节点时，进入 else 分支

   • 执行 prev->next = pcur->next（设置为 NULL）

   • 执行 newTail->next = pcur（将节点移到末尾）

   • 执行 pcur->next = NULL 和 newTail = pcur

   • 执行 pcur = prev->next（变为 NULL）

   • 循环条件 while(pcur != NULL) 不满足，循环结束

SLNode* partition(SLNode* phead, int x)
{if(phead || phead->next){return phead;}SLNode* ptail = phead;while(ptail->next){ptail = ptail->next;}SLNode* newTail = ptail;SLNode* newHead = (SLNode*)malloc(sizeof(SLNode));newHead->next = phead;SLNode* prev = newHead;SLNode* pcur = phead;while(pcur){if(pcur->val > x){prev = pcur;pcur = pcur->next;}else{prev->next = pcur->next;newTail->next = pcur;pcur->next = NULL;newTail = pcur;pcur = prev->next;}}SLNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}