问题一：删除链表中特定值节点(LC203)

（一）问题描述

给定链表头节点head和整数val，删除所有值等于val的节点，返回新头节点。

示例1：

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

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]

（二）解题思路

思路1： 遍历数组，值等于val则释放当前节点

思路2： 创建新链表，值不等于val则尾插到新链表

（三）代码实现（思路2）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode LN;
struct ListNode* removeElements(struct ListNode* head, int val) {
    LN* newHead = NULL;
    LN* newTail = NULL;

    LN* pcur = head;
    while(pcur)
    {
        if(pcur->val!=val)
        {
            //为空
            if(newHead==NULL)
            {
                newHead=pcur;
                newTail=pcur;
            }
            else
            {
                newTail->next=pcur;
                newTail=newTail->next;
            }
        }
        pcur=pcur->next;
    }
    if(newTail!=NULL)
        newTail->next=NULL;
    return newHead;
}

（四）代码解析

1. 化新链表头尾指针： 用 newHead 记录新链表头节点，newTail 维护新链表尾节点，初始均为 NULL 。
2. 遍历原链表： 通过 pcur 指针遍历输入的原链表 head 。
3. 筛选保留节点： 遇到值不等于 val 的节点时，若新链表为空（newHead 是 NULL ），该节点同时作为新链表的头和尾；若新链表非空，将该节点链接到新链表尾部，更新 newTail。
4. 处理新链表尾节点： 遍历结束后，将新链表尾节点的 next 置为 NULL。如果没有这行代码，节点5依旧指向原来指向的节点（也就是节点6），返回的链表就是[1,2,3,4,5,6]
   

问题二：反转链表(LC206)

（一）问题描述

给定链表头节点，反转链表并返回新头节点。

示例1：

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

示例2：

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

示例 3：
输入：head = []
输出：[]

（二）解题思路

思路1： 创建一个新的链表，依次头插在新链表前
思路2：创建3个指针完成链表翻转

（三）代码实现（思路2）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode LN;
struct ListNode* reverseList(struct ListNode* head) {

    if (head == NULL)
        return head;
    LN* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;
    while (n2 != NULL)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

（四）代码解析

1. 指针初始化：n1 初始化为 NULL（表示反转后当前节点的前一个节点，初始时没有节点，所以为 NULL ），n2 初始化为 head（从原链表头节点开始处理 ），n3 初始化为 head->next（提前保存当前节点的下一个节点，防止后续指针修改后找不到 ）。
2. 反转循环：在 while (n2 != NULL) 循环中：
   n2->next = n1; 实现当前节点 n2 指向其前一个节点 n1 ，完成指针反转。
   然后 n1 = n2; n2 = n3; 让三个指针依次向后移动，准备处理下一个节点。
   if (n3 != NULL) 判断下一个节点是否存在，存在则更新 n3 = n3->next ，保证循环能持续推进。
3. 返回结果：当循环结束时，n2 为 NULL ，此时 n1 指向的就是反转后链表的头节点，返回 n1 。

问题三：合并两个有序链表(LC21)

（一）问题描述

将两个升序链表合并为一个新升序链表返回。

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

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

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

（二）解题思路

• 创建新链表，遍历原来两个链表，将较小值尾插到新链表
• 遍历结果只有两种：l1为空或者l2为空
• 把不为空的l1或l2尾插到新链表

（三）代码实现

 typedef struct ListNode LN;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    LN* l1 = list1;
    LN* l2 = list2;

    if(l1==NULL)
    return l2;
    if(l2==NULL)
    return l1;

    LN* newHead = NULL;
    LN* newTail = NULL;

    while(l1&&l2)
    {
        if(l1->val < l2->val)
        {
            if(newHead==NULL)
            {
                newHead = newTail = l1;
            }
            else
            {
                newTail->next=l1;
                newTail = newTail->next;
            }
            l1=l1->next;
        }
        else
        {
            if(newHead==NULL)
            {
                newHead = newTail = l2;
            }
            else
            {
                newTail->next=l2;
                newTail = newTail->next;
            }
            l2=l2->next;
        }
    }
    if(l1)
    {
        newTail->next=l1;
    }
    if(l2)
    {
        newTail->next=l2;
    }
    return newHead;
}

优化后：

 typedef struct ListNode LN;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    LN* l1 = list1;
    LN* l2 = list2;

    if(l1==NULL)
    return l2;
    if(l2==NULL)
    return l1;

    LN* newHead = NULL;
    LN* newTail = NULL;

    newHead = newTail = (LN*)malloc(sizeof(LN));

    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;
    }

    LN* ret = newHead->next;
    free(newHead);
    newHead=NULL;
    return ret;
}

注意： 动态开辟的内存要手动释放

问题四：找链表中间节点(LC876)

（一）问题描述

找到单链表中间节点，若有两个中间节点，返回第二个。

示例1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例2:

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

（二）解题思路

思路1：计数器遍历链表，得到总数，再遍历一半找到中间节点
思路2：快指针fast每次走两步，慢指针slow每次走一步。当fast走到末尾，slow指向中间节点。

（三）代码实现

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

注意：

• 奇数个节点：fast走到最后，恰好slow走到中间节点
• 偶数个节点：fast就需要走到空，slow走到第二个中间节点

因此循环条件：fast && fast->next 顺序不可以更改，因为&&存在逻辑短路，当fast为空就不会对fast解引用访问

问题五：链表分割（按值分区）(面试题02.04)

（一）问题描述

给定链表头节点和特定值x，使所有小于x的节点在大于等于x节点之前，无需保留原相对位置。

示例1:

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

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

（二）解题思路

• 思路1: 在原链表上进行修改,
  • 若pcur值小于x,往后走
  • 若大于或等于x,尾插在链表后,删除旧节点
• 思路2: 创建新链表,遍历原链表
  • 若pcur值小于x,则头插在新链表中
  • 若大于或等于x,尾插在链表后
• 思路3: 创建小链表和大链表
  • 若pcur小于x值尾插小链表
  • 大于或等于x值尾插在大链表
  • 小链表尾节点和大链表头节点相连

（三）代码实现(思路3)

typedef struct ListNode LN;
struct ListNode* partition(struct ListNode* head, int x) {
    if(head==NULL)
    return NULL;

    LN* lessHead,*lessTail,*greaterHead,*greaterTail;
    lessHead = lessTail = (LN*)malloc(sizeof(LN));
    greaterHead = greaterTail = (LN*)malloc(sizeof(LN));

    LN* pcur = head;
    while(pcur)
    {
        if(pcur->val < x)
        {
            lessTail->next = pcur;
            lessTail = lessTail->next;
        }else{
            greaterTail->next = pcur;
            greaterTail = greaterTail->next;
        }
        pcur = pcur->next;
    }
     
    //把尾节点下一个节点置为空,如果不写这行代码会出现死循环(5->2)
    greaterTail->next = NULL;
    //两个链表相连
    lessTail->next = greaterHead->next;

    LN* tmp = lessHead->next;
    free(lessHead);
    lessHead = NULL;
    free(greaterHead);
    greaterHead = NULL;
    return tmp;
}

问题六：约瑟夫环问题

（一）问题描述

n个人围成圈，从第1人开始报数，报到m的人离开，最后留下的人编号是多少。

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

示例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

示例2
输入：1,1
返回值：1

（二）解题思路

1. 根据n创建带环链表
2. 遍历带环链表,计数器来模拟报数

（三）代码实现

typedef struct ListNode LN;
LN* buyListNode(int val)
{
    LN* newNode = (LN*)malloc(sizeof(LN));
    newNode->val=val;
    return newNode;
}
LN* createCircle(int n)
{
    LN* phead=(LN*)malloc(sizeof(LN));
    LN* ptail = phead;
    // 初始化头节点值为1
    phead->val = 1;
    // 创建2到n号节点
    for(int i = 2;i <= n;i++)
    {
        ptail->next=buyListNode(i);
        ptail=ptail->next;
    }
    // 尾节点指向头节点，形成环
    ptail->next=phead;
    return ptail;
}
int ysf(int n, int m ) {
    LN* prev = createCircle(n);  // prev指向尾节点
    LN* pcur = prev->next;       // pcur指向头节点（第一个人）
    int count = 1;               // 报数计数器
    
    // 当只剩一个节点时结束循环
    while(pcur->next!=pcur)
    {
        // 当报数到 m时，移除当前节点
        if(count==m)
        {
            prev->next=pcur->next;  // 跳过当前节点
            free(pcur);             // 释放内存
            pcur=prev->next;        // 移动到下一个节点
            count=1;                // 重置计数器
        }else {
            // 未报数到 m，继续移动指针
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    // 返回最后剩下的节点的值
    return pcur->val;
}

（四）代码解析

• 使用 prev 和 pcur 两个指针追踪当前节点和前一个节点
• count 变量记录当前报数
• 当 count 等于 m 时：
  • 将前一个节点的 next 指向当前节点的 next，实现当前节点的移除
  • 释放被移除节点的内存
  • 重置计数器，继续下一轮报数
• 循环终止条件：当链表中只剩一个节点（pcur->next == pcur）