数据结构初阶：顺序表与链表精选 15 道 OJ 练习

88. 合并两个有序数组

题目介绍

方法一

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 思路：使用类似归并排序的最后一步：双路归并（遍历两个容器的三指针）
    int tmp[n + m];
    int p1 = 0, p2 = 0, pi = 0;
    for (; p1 < m && p2 < n; pi++) {
        if (nums1[p1] <= nums2[p2]) tmp[pi] = nums1[p1++];
        else tmp[pi] = nums2[p2++];
    }
    while (p1 < m) tmp[pi++] = nums1[p1++];
    while (p2 < n) tmp[pi++] = nums2[p2++];
    for (int i = 0; i < m + n; i++) nums1[i] = tmp[i];
    return;
}

方法二

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    // 思路：从后往前比较两个数组中元素的大小，将大的元素添加到 nums1 数组的末尾
    // 1. 定义三个指针分别指向：
    // l1 指向 nums1 的最后一个有效元素（m-1）
    // l2 指向 nums2 的最后一个元素（n-1）
    // l3 指向 nums1 的最后一个位置（m+n-1）
    int l1 = m - 1, l2 = n - 1;
    int l3 = m + n - 1;
    // 2. 从后向前进行比较合并，知道其中一个数组中的元素已经遍历完了
    while (l1 >= 0 && l2 >= 0) {
        if (nums1[l1] < nums2[l2]) nums1[l3--] = nums2[l2--];
        else nums1[l3--] = nums1[l1--];
    }
    // 循环结束后有两种情况：
    // 1) l1 >= 0：nums1 中剩余元素已经在正确位置，无需处理
    // 2) l2 >= 0：nums2 中还有剩余元素未合并
    // 只需要处理第二种情况：将 nums2 剩余元素复制到 nums1 前端
    while (l2 >= 0) {
        nums1[l3--] = nums2[l2--];
    }
    return;
}

链表 OJ 练习

面试题 02.02. 返回倒数第 k 个节点

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        // 思考：如果这道题是返回数组中倒数第 K 个元素的值，那简直就是小菜一碟
        // 为自己添加额外的条件：
        // 1. 空间复杂度 O(1) （有人想着将链表中的节点都存到数组中，但是被限制）
        // 2. 只能遍历链表一次 （有人想着将链表进行逆序，然后遍历链表直接访问链表的第 k 个元素）
        // 正确的思路：
        // 1. 使用两个相差 k 个节点距离的指针，然后让两个指针同时走，
        // 2. 当在前面的快指针指向空的时候，慢指针指向的节点就是我们想要的答案
        ListNode *first = head, *last = head;
        while (k--) first = first->next;
        // 一次遍历整个链表
        for (; first != nullptr;) {
            first = first->next;
            last = last->next;
        }
        return last->val;
    }
};

OR36 链表的回文结构

题目介绍

方法一

判断链表是否为回文链表 = 反转单向链表 反转单向链表 = 寻找单向链表的中间节点

实现：寻找链表的中间节点

/**
 * @brief 寻找链表的中间节点（快慢指针法）
 * @param head 链表头节点指针
 * @return 中间节点指针
 *
 * 原理：快指针每次走两步，慢指针每次走一步，
 * 当快指针到达链表末尾时，慢指针正好在中间。
 */
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

代码片段解释：

while (fast && fast->next)

这个循环条件是快慢指针法寻找链表中间节点的核心安全保证，其精妙之处在于同时防范了两种可能的越界情况：

第一种情况：开始的情况

输入情况	条件表现	结果正确性
空链表	fast 初始为 null → 不进入循环	返回 null
单节点链表	fast->next 为 null → 不进入循环	返回 head

第二种情况：结束的情况

检查条件	防护场景	示例说明
fast != nullptr	防止访问 nullptr->next 的非法操作	当链表节点数为奇数时，快指针最后停在最后一个节点（fast->next == nullptr）
fast->next != nullptr	确保能安全执行 fast->next->next	当链表节点数为偶数时，快指针最后会走到空指针（fast = nullptr）

实现：反转单向链表

/**
 * @brief 反转单向链表（三指针法）
 * @param head 链表头指针的引用（注意：会修改原始头指针）
 * @return 反转后的新链表头指针
 *
 * 算法原理：
 * 使用三个指针协同工作：
 * 1. newHead：始终指向已反转部分链表的头部
 * 2. curr：当前待反转的节点
 * 3. next：保存 curr 原下一个节点的临时指针
 *
 * 时间复杂度：O(n)
 * 空间复杂度：O(1)
 */
ListNode* reverseList(ListNode*& head) // 参数是头指针的引用（会修改原指针）
{
    ListNode* next = nullptr;
    ListNode* newHead = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        next = curr->next;
        curr->next = newHead;
        newHead = curr;
        curr = next;
    }
    head = newHead;
    return head;
}

bool chkPalindrome(ListNode* A) {
    struct ListNode* mid = middleNode(A);
    struct ListNode* rmid = reverseList(mid);
    while (rmid && A) {
        if (rmid->val != A->val) return false;
        rmid = rmid->next;
        A = A->next;
    }
    return true;
}

综合：判断链表是否为回文链表

/* struct ListNode { 
 *     int val; 
 *     struct ListNode *next; 
 *     ListNode(int x) : val(x), next(NULL) {} 
 * }; */
class PalindromeList {
public:
    // 实现：寻找链表的中间节点：
    ListNode* middleNode(ListNode* head) {
        // 1. 定义两个指针，并初始为头节点
        ListNode* fast = head;
        ListNode* slow = head;
        // 2. 使用 while 更新双指针
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 3. 返回结果
        return slow;
    }
    
    ListNode* reverseList(ListNode* head) {
        // 1. 定义三个指针并对其进行初始化
        ListNode* next = nullptr;
        ListNode* newHead = nullptr;
        ListNode* curr = head;
        // 2. 使用一个 while 循环遍历整个链表
        while (curr != nullptr) {
            next = curr->next;
            curr->next = newHead;
            newHead = curr;
            curr = next;
        }
        // 3. 更新头节点
        head = newHead;
        return head;
    }
    
    bool chkPalindrome(ListNode* A) {
        // 时间复杂度 O(n)：意味着：我们只能遍历链表一次
        // 空间复杂度 O(1)：意味着：我们不能额外的开辟一个数组的空间
        // 1. 得到链表的中间节点
        ListNode* mid = middleNode(A);
        // 2. 得到后半部分反转之后的链表
        ListNode* rmid = reverseList(mid);
        while (rmid) {
            if (A->val != rmid->val) return false;
            A = A->next;
            rmid = rmid->next;
        }
        return true;
    }
};

160. 相交链表

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        // 代码逻辑分为两部分：1. 判断连个单链表是不是相交链表 2. 如果是返回相交的节点
        // 任务 1：只需判断两个链表的尾节点的地址是否相等即可（也可以理解为判断两个指针是否相等）
        // 任务 2：使用双指针遍历两个链表，何时两个指针的值相等时候，那么指针指向的节点就是开始相交的节点
        // 1. ListNode *tmpA=headA,*tmpB=headB;
        int lenA = 1, lenB = 1;
        while (tmpA->next) { tmpA = tmpA->next; lenA++; }
        while (tmpB->next) { tmpB = tmpB->next; lenB++; }
        if (tmpA != tmpB) return nullptr;
        // 2.
        // 想要完成任务 2 我们要保证两个指针是从同一个位置开始进行遍历的
        // 所以：我们应该想让长度长的链表的头指针向后移动到持平
        // 到底哪个链表的长度更长呢？---> 使用假设法
        int gap = abs(lenA - lenB);
        ListNode *longList = headA, *shortList = headB;
        if (lenB > lenA) {
            longList = headB;
            shortList = headA;
        }
        while (gap--) {
            longList = longList->next;
        }
        while (longList != nullptr) {
            if (longList == shortList) return longList;
            longList = longList->next;
            shortList = shortList->next;
        }
        return nullptr;
    }
};

141. 环形链表

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        // 思路：使用快慢指针
        ListNode *fast = head, *slow = head;
        while (fast && fast->next) // 若指针一次可以走两步的话，就是使用这种方式遍历整个链表
        {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) return true;
        }
        return false;
    }
};

思考与探究

142. 环形链表 II

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 使用双指针
        ListNode *fast = head, *slow = head;
        // 遍历环形链表，并找到快指针和慢指针相遇的地方 (若没有相遇，条件会为空，代表链表没有环)
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (fast == slow) {
                ListNode* meet = fast;
                // 遍历环形链表，并使用对撞指针找到链表开始入环的第一个节点
                while (head != meet) {
                    head = head->next;
                    meet = meet->next;
                }
                return meet;
            }
        }
        return nullptr;
    }
};

思考与探究

138. 随机链表的复制

题目介绍

方法一

/* // Definition for a Node.
class Node {
 public:
  int val;
  Node* next;
  Node* random;
  Node(int _val) {
    val = _val;
    next = NULL;
    random = NULL;
  }
}; */
class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 对链表进行深拷贝的步骤：
        // 步骤 1：拷贝节点插在原节点的后面
        // 步骤 2：控制 random 指针
        // 步骤 3：把拷贝节点取下来尾插成新的链表
        // 1.
        Node* curr = head;
        while (curr != nullptr) {
            // 1) 创建节点
            Node* copy = new Node(curr->val);
            // 2) 插入节点
            copy->next = curr->next;
            curr->next = copy;
            // 3) 指针移动
            curr = copy->next;
        }
        // 2.
        // 情况 1：curr 指针指向的节点的 random 指向的 null，那么 copy 指针指向的节点的 random 指向的也是 null
        // 情况 2：curr 指针指向的节点的 random 指向的是某节点，那么 copy 指针指向的节点的 random 指向的是：curr->random->next;
        curr = head;
        while (curr != nullptr) {
            // 1) 创建指针
            Node* copy = curr->next;
            // 2) 控制 random 指针
            if (curr->random == nullptr) copy->random = nullptr;
            else copy->random = curr->random->next;
            // 3) 指针移动
            curr = copy->next;
        }
        // 3.
        // 1) 需要使用两个指针遍历两个链表 ---> curr 和 copy
        // 2) 需要使用两个指针：一个保存新链表的头节点、一个处理新链表的 next 指针
        // ---> copyhead 和 copytail
        // 3) 需要一个指针存储遍历的指针的下一位置 --> next
        // 因为：在遍历的过程中我们要更改访问到的节点的 next 指针
        // 0) 创建需要根据具体的情况进行更新的指针 + 重置遍历使用的指针
        Node *copyhead = nullptr, *copytail = nullptr;
        curr = head;
        while (curr != nullptr) {
            // 1) 创建每次都要实时更新的指针
            Node* copy = curr->next;
            Node* next = copy->next;
            // 2) 核心的剔出新链表的操作（删除操作）
            if (copyhead == nullptr) copyhead = copytail = copy;
            else {
                copytail->next = copy;
                copytail = copy;
            }
            curr->next = copy->next;
            // 3) 移动指针
            curr = next;
        }
        return copyhead;
    }
};

程序执行流程

203. 移除链表元素

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    // 思路 1 ---> 本质：在原链表中遍历并将值为 val 的节点删除掉
    // 1. 我们可以再使用一个 prev 指针去遍历这个链表
    // 2. 如果这个 prev 指针的下一个节点的值等于 val 的话，就将下一个节点删除掉
    // 0. 处理特殊的情况：
    // 情况二：这个链表中有一个或多个节点，并且头节点的值等于 val（或者头节点之后连续的出现了多个值为 val 的节点）
    while (head != NULL && head->val == val) {
        struct ListNode* del = head;
        head = head->next;
        free(del);
    }
    // 情况一：这个链表中没有节点
    if (head == NULL) return NULL;
    // 1. 定义一个 prev 指针指向链表的头指针进行遍历
    struct ListNode* prev = head;
    while (prev->next != NULL) {
        // 2. 使用 if 判断：如果下一个节点是我们要删除的节点
        if (prev->next->val == val) {
            // 2.1：定义一个指针指向我们要删除的节点
            struct ListNode* del = prev->next;
            // 2.2：断开要删除节点的连接
            prev->next = prev->next->next;
            // 2.3：释放要删除节点的内存空间
            free(del);
        }
        // 这里使用 if - else 条件语句原因是：要删除的节点可能是连续的，所以我们不一定每次都要向后移动一次
        // 3. 将 prev 指针往后移动
        else {
            prev = prev->next;
        }
    }
    return head;
}

代码片段解释

疑问：为什么要将情况 2 写在情况 1 之前，这样你还有多此一举在 while 循环写一个：head!=NULL&&？

回答：大家提出的这个问题是真的不错啊！！！

但是你心中的这个疑问可以使用下面的这个测试样例来解答

**当链表的所有节点都等于 val 时（例如 [6,6,6]，val=6）**你的 while (head->val == val) 循环会一直删除头节点，直到 head 变为 NULL但 while (prev->next != NULL) 循环仍然会执行，而 prev 已经是 NULL，导致 访问 prev->next 时出现空指针解引用（Segmentation Fault）

所以：在 while (head->val == val) 循环结束后，必须检查 head 是否为 NULL，如果是，直接返回 NULL，避免后续操作。在 while (head->val == val) 循环中增加 head != NULL 检查，确保在 head 变为 NULL 时停止循环。

方法二

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    // 思路 2 --> 本质：在原链表中遍历并将值不为 val 的节点尾插到新链表中
    // 1. 我们可以再使用一个 pcur 指针去遍历这个链表
    // 2. 如果 pcur 指针指向的节点的值不等于 val 的话，就将该节点尾插到新链表中
    // 1. 用于遍历链表 ---> pcur
    // 2. 用于记录首元节点的位置 ---> phead
    // 3. 用于进行尾插 ---> ptail
    struct ListNode* pcur = head;
    struct ListNode* phead = NULL, *ptail = NULL;
    while (pcur != NULL) {
        if (pcur->val != val) {
            // 情况 1：当链表为空链表时候（第一次插入时候）
            if (phead == NULL) {
                phead = ptail = pcur;
            }
            // 情况 2：当链表为非空链表时候
            else {
                ptail->next = pcur;
                ptail = ptail->next;
            }
        }
        pcur = pcur->next;
    }
    if (ptail != NULL) ptail->next = NULL; // 注意：这里要将尾指针的下一个位置置空
    // 因为：我们本质上并不是创建了一个新的链表，而是在原链表的基础进行了新的连接
    // 当面对测试样例：[1,2,6,3,4,5,6] 6 如果不置空的话，输出会多输出一个 6
    return phead;
}

206. 反转链表

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    // 思路 1：本质 ---> 遍历原链表的所有的节点并将其进行头插入到新链表中（本质上并没有创建新的单链表）
    // 1. 定义一个 pcur 指针遍历链表中的所有的节点
    // 2. 并将遍历到的每个节点进行头插
    // 1. 用于遍历链表 ---> pcur
    // 2. 用于记录新链表的首元节点 ---> phead
    struct ListNode* pcur = head;
    struct ListNode* phead = NULL;
    while (pcur != NULL) {
        // 3. 用于记录 pcur 所指节点的下一个节点
        struct ListNode* next = pcur->next;
        pcur->next = phead;
        phead = pcur;
        pcur = next;
    }
    return phead;
}

876. 链表的中间结点

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
    // 思路：
    // 1. 使用遍历同一个链表的快慢指针
    // 2. 快指针一次走两步，慢指针一次走一步
    // 3. 当快指针到达链表的尾节点时，慢指针正好指向链表的中间节点
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    // 注意 1：fast 不为空对应：偶数个节点的结束遍历的情况
    // 注意 2：fast->next 不为空对应：奇数个节点的结束遍历的情况
    // 注意 3：这两个判断条件不能写颠倒
    while (fast != NULL && fast->next != NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

21. 合并两个有序链表

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 思路：有点类似归并排序最后的操作'两个数组中元素的双路归并'
    // 1. 使用两个临时的指针分别遍历两个链表中的所有的节点
    // 2. 比较遍历到的两个节点的值的大小
    // 3. 值小的节点尾插到新的链表中
    // 两个链表可能出现的所有的情况
    // 1. 两个链表中：两个链表都为空
    // 2. 两个链表中：一个链表为空，另一个链表不为空
    // 3. 两个链表中：两个链表都为不空
    // 处理特殊情况：两个链表都为空
    if (list1 == NULL && list2 == NULL) return NULL;
    // 处理特殊情况：一个链表为空，另一个链表不为空
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    // 1. 定义两个链表的临时指针遍历两个链表 ---> pcur1 和 pcur2
    struct ListNode* pcur1 = list1;
    struct ListNode* pcur2 = list2;
    // 2. 用于记录新链表的首元节点的位置 ---> phead
    // 3. 用于进行尾插 ----> ptail
    struct ListNode* phead = NULL;
    struct ListNode* ptail = NULL;
    while (pcur1 != NULL && pcur2 != NULL) // 当其中有一个链表遍历结束时整个合并阶段基本上就算是完成任务了 --->两个链表都不为空链表的时候可以进入循环
    {
        if (pcur1->val <= pcur2->val) {
            // 情况 1：空链表的插入（第一向新链表中进行插入）
            if (phead == NULL) {
                phead = ptail = pcur1;
            }
            // 情况 2：非空链表的插入
            else {
                ptail->next = pcur1;
                ptail = ptail->next;
            }
            pcur1 = pcur1->next;
        } else {
            // 情况 1：空链表的插入（第一向新链表中进行插入）
            if (phead == NULL) {
                phead = ptail = pcur2;
            }
            // 情况 2：非空链表的插入
            else {
                ptail->next = pcur2;
                ptail = ptail->next;
            }
            pcur2 = pcur2->next;
        }
    }
    // 当其中一个链表已经遍历完之后，只需要将其中的另一个链表中的剩余的节点尾插到新链表中即可
    if (pcur1 == NULL) {
        ptail->next = pcur2;
    } else {
        ptail->next = pcur1;
    }
    return phead;
}

方法二：使用哨兵位进行优化

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 思路：两个链表进行合并的过程 --> 本质：单链表的尾插 -> 需要考虑被插链表是否为空链表的情况
    // 所以：我们直接将在被插链表中创建一个新的节点'哨兵节点'（保证其一定为非空链表）--> 带头节点的链表
    // 1. 使用两个临时的指针分别遍历两个链表中的所有的节点
    // 2. 比较遍历到的两个节点的值的大小
    // 3. 值小的节点尾插到新的链表中
    // 两个链表可能出现的所有的情况
    // 1. 两个链表中：两个链表都为空
    // 2. 两个链表中：一个链表为空，另一个链表不为空
    // 3. 两个链表中：两个链表都为不空
    // 处理特殊情况：两个链表都为空
    if (list1 == NULL && list2 == NULL) return NULL;
    // 处理特殊情况：一个链表为空，另一个链表不为空
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    // 1. 定义两个链表的临时指针遍历两个链表 ---> pcur1 和 pcur2
    struct ListNode* pcur1 = list1;
    struct ListNode* pcur2 = list2;
    // 2. 用于记录新链表的首元节点的位置 ---> phead
    // 3. 用于进行尾插 ----> ptail
    struct ListNode* phead = NULL;
    struct ListNode* ptail = NULL;
    // 4. 创建哨兵节点
    phead = ptail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (pcur1 != NULL && pcur2 != NULL) // 当其中有一个链表遍历结束时整个合并阶段基本上就算是完成任务了 --->两个链表都不为空链表的时候可以进入循环
    {
        if (pcur1->val <= pcur2->val) {
            ptail->next = pcur1;
            ptail = ptail->next;
            pcur1 = pcur1->next;
        } else {
            ptail->next = pcur2;
            ptail = ptail->next;
            pcur2 = pcur2->next;
        }
    }
    // 当其中一个链表已经遍历完之后，只需要将其中的另一个链表中的剩余的节点尾插到新链表中即可
    if (pcur1 == NULL) {
        ptail->next = pcur2;
    } else {
        ptail->next = pcur1;
    }
    // 释放哨兵节点
    struct ListNode* next = phead->next;
    free(phead);
    phead = next;
    return phead;
}

环形链表的约瑟夫问题

题目介绍

方法一

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int 整型
 * @param m int 整型
 * @return int 整型
 */
// 实现：'链表节点的创建'的辅助函数
struct ListNode* CreateNode(int x) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (newNode == NULL) {
        exit(1);
    }
    newNode->val = x;
    newNode->next = NULL;
    return newNode;
}
// 实现：'将链表的节点连接成环形链表'的辅助函数
struct ListNode* CreateCircle(int n) {
    // 1.1：先创建一个首元节点
    struct ListNode* phead = CreateNode(1);
    // 1.2：再使用 for 循环创建出 2~n 的节点
    struct ListNode* ptail = phead;
    for (int i = 2; i <= n; i++) {
        ptail->next = CreateNode(i);
        ptail = ptail->next;
    }
    // 1.3：使创建出来的节点形成环形链表
    ptail->next = phead;
    // 2. return ptail;
    // 由于接下来我们要对该环形链表进行删除的操作，
    // 所以这里我们要返回头指针前面的那个指针：尾指针
}
int ysf(int n, int m) {
    // 思路：
    // 1. 创建 n 个节点的单链表，每个节点的值分别设置为 1~n
    // 2. 遍历单链表，并记录当前的报数
    // 3. 当报数的值为 m 时，删除该节点
    // 1. 定义临时指针进行遍历环形链表 --> pcur
    // 2. 用于删除下一个节点 ---> prev
    struct ListNode* prev = CreateCircle(n);
    struct ListNode* pcur = prev->next;
    int count = 1;
    // 此时 while(pcur->next!=pcur)// 当环形链表中只剩下一个节点的时候：该节点的下一个节点还是本身：
    while (pcur->next != pcur) {
        // 1. if(count==m){ prev->next=pcur->next;free(pcur); pcur=prev->next; count=1;//重置报数}
        // 2. else{ prev=prev->next; pcur=pcur->next; count++;}
        if (count == m) {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        } else {
            prev = prev->next;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}

面试题 02.04. 分割链表

题目介绍

方法一

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    // 思路 1：使用一个指针遍历整个链表如果遍历到的节点的值大于等于特定值 x 的话就将它尾插的原链表
    // 处理特殊的情况：'空链表 + 链表中只有一个节点'
    if (head == NULL || head->next == NULL) {
        return head;
    }
    // 0. 原链表的尾指针 ---> ptail
    // 1. 记录新链表的首元节点 ---> newHead
    // 2. 用于尾插 --> newTail
    // 3. 用于遍历整个链表 ---> pcur
    // 4. 用于删除下一个节点 ---> prev
    struct ListNode* ptail = head;
    struct ListNode* newHead = head, *newTail = head;
    struct ListNode* pcur = head;
    struct ListNode* prev = NULL;
    while (ptail->next != NULL) {
        ptail = ptail->next;
    }
    newTail = ptail;
    while (pcur != ptail) {
        if (pcur->val >= x) {
            /*--------------第一阶段：将大于或等于特定值 x 的节点删除掉--------------*/
            struct ListNode* next = pcur->next;
            // 但是你要明白在一个链表中将一个节点删除要分类讨论
            // 情况 1：要删除的节点是头节点 ---> 相当于头删
            if (prev == NULL) {
                // 1. 断 newHead=pcur->next;
                // 2. 释
                // 3. 移
                // pcur=pcur->next; 不能立即移动 pcur，因为还需要将这个节点尾插到链表尾部
            }
            // 情况 2：要删除的节点不是头节点 ---> 相当于尾删
            else {
                // 1. 断 prev->next=pcur->next;
                // 2. 释
                // 3. 移
                // pcur=pcur->next;
                // prev=prev->next;
            }
            /*--------------第二阶段：将断连的节点尾插的原链表的后面--------------*/
            // 1. 连 newTail->next=pcur;
            // 2. 移 newTail=newTail->next; newTail->next =NULL;// 防止成环
            pcur = next;
            // 这个时候再移动 pcur
        } else {
            prev = pcur;
            pcur = pcur->next;
        }
    }
    return newHead;
}

*疑问：上面的代码中为什么需要注释那些代码？*关于释放节点（释）：原始代码中注释掉了释放节点的操作，因为：我们不是要真正删除节点，而是将它移动到链表尾部如果调用 free(pcur)，节点就被销毁了，无法再使用它进行尾插关于移动指针（移）：原始代码中 pcur=pcur->next 和 prev=prev->next 被注释，因为：我们需要先完成当前节点的尾插操作，才能移动指针在第二阶段（尾插部分）统一处理指针移动更安全

方法二

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x) {
    // 思路 2：将原链表的节点值<特定值 x 的节点添加到小链表中，否则添加到大链表中，最后将这两个链表首尾相连
    // 处理特殊的情况：'空链表 + 链表中只有一个节点'
    if (head == NULL || head->next == NULL) return head;
    /*---------------第一阶段：创建两个带头节点的链表---------------*/
    struct ListNode* lessHead, *lessTail;
    struct ListNode* greaterHead, *greaterTail;
    lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    lessHead->next = NULL;
    greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterHead->next = NULL;
    /*---------------第二阶段：填充两个带头节点的链表---------------*/
    struct ListNode* pcur = head;
    while (pcur != NULL) {
        // 1. 填充小链表
        // 注意：向一个链表中插入一个节点应该判断：'链表是否为空'，但是我们使用了哨兵节点之后就不需要进行判断了，直接进行插入
        if (pcur->val < x) {
            lessTail->next = pcur;
            lessTail = lessTail->next;
        }
        // 2. 填充大链表
        else {
            greaterTail->next = pcur;
            greaterTail = greaterTail->next;
        }
        pcur = pcur->next;
    }
    /*---------------第三阶段：连接两个带头节点的链表---------------*/
    lessTail->next = greaterHead->next;
    greaterTail->next = NULL; // 防止成环
    /*---------------第四阶段：释放哨兵节点---------------*/
    struct ListNode* ret = lessHead->next;
    free(lessHead);
    lessHead = NULL;
    free(greaterHead);
    greaterHead = NULL;
    return ret;
}