【数据结构初阶】单链表经典算法题十道（详解+图例）—得道飞升（上篇）

单链表是数据结构里最基础、也最适合练手的一块。这一篇挑了四道经典题：移除元素、反转链表、找中间节点、合并两个有序链表，每道都给出思路和可直接跑的代码，顺带把几个容易踩的坑讲清楚。

一、移除元素

思路：新建一个链表（newhead、newtail），遍历原链表，把值不等于 val 的结点尾插到新链表里。

typedef struct ListNode ListNode;

struct ListNode* removeElements(struct ListNode* head, int val) {
    // 创建新链表
    ListNode* newhead;
    ListNode* newtail;
    newhead = newtail = NULL;

    // 遍历原链表
    ListNode* pcur = head;
    while (pcur) {
        if (pcur->val != val) {
            // 又分两种情况：链表为空，不为空
            if (newhead == NULL) {
                newtail = newhead = pcur;
            } else {
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }

    // [7,7,7,7,7]，val=7 时 newtail 仍是 NULL，不能解引用，所以要加 if
    if (newtail)
        newtail->next = NULL;

    return newhead;
}

注意：

• 当原链表为空时，newhead = newtail = pcur 的情况要能正确处理。
• 遍历到最后时，被保留的最后一个结点，它的 next 仍然指向原链表中后面的结点，比如把 6 后面那个 7 删掉后，返回的链尾还挂着 6，所以必须显式把尾结点的 next 置为 NULL。
• 最后那个 if (newtail) newtail->next = NULL; 不是多余的防御，而是必须——整个链表都被删光时 newtail 是空指针。

二、反转链表

思路：三个指针一次走一遍，把每个节点的next掉头。

struct ListNode* reverseList(struct ListNode* head) {
    // 链表也有可能是空链表
    if (head == NULL) {
        return head;
    }

    // 定义三个指针变量
    ListNode *n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = n2->next;

    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    return n1;
}

循环结束时 n2 为空，n1 停在原链表的尾结点，也正是反转之后的新头，所以返回 n1。

三、链表的中间节点

思路：快慢指针。慢指针每次走一步，快指针每次走两步，两者同起点。

struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    // 注意 while (fast && fast->next)，顺序不可互换：
    // 偶数个结点时 fast == NULL 循环就结束了，
    // 若写成 while (fast->next && fast)，会先解引用空指针而报错

    while (fast && fast->next) {
        slow = slow->next;              // 慢指针每次走一步
        fast = fast->next->next;        // 快指针每次走两步
    }

    // 此时 slow 指向的结点恰好是中间结点
    return slow;
}

为什么快慢指针能找到中心？设链表长度为 n，快指针走的路程是慢指针的两倍，即 2×慢 = 快 = n，所以慢指针只走了 n/2，正好落在中间位置。奇数个结点时 slow 停在正中间，偶数个结点时停在后两个的中间那个，也就是靠后那个。

四、合并两个有序链表

思路：新建链表，newhead、newtail 指向它的头，再用两个指针分别指向两条原链表的头，比较数据大小，谁小谁尾插。

1. 先处理边界与空表

if (list1 == NULL) return list2;
if (list2 == NULL) return list1;

2. 尾插版本

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;

    ListNode* l1 = list1;
    ListNode* l2 = list2;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            if (newtail == NULL) {
                newtail = newhead = l1;
            } else {
                newtail->next = l1;
                newtail = newtail->next;
            }
            l1 = l1->next;
        } else {
            if (newhead == NULL) {
                newtail = newhead = l2;
            } else {
                newtail->next = l2;
                newtail = newtail->next;
            }
            l2 = l2->next;
        }
    }

    // 出循环时要么 l1 == NULL，要么 l2 == NULL
    // 这里不需要 while 循环，把剩下那段直接挂上去即可
    if (l1) newtail->next = l1;
    if (l2) newtail->next = l2;

    return newhead;
}

3. 优化版：先申请一个不为空的头结点

申请一个哨兵头结点之后，就再也不用判断新链表是否为空了。最后记得 free 掉哨兵。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    ListNode* newhead;
    ListNode* newtail;
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* l1 = list1;
    ListNode* l2 = list2;

    while (l1 && l2) {
        if (l1->val <= l2->val) {
            newtail->next = l1;
            l1 = l1->next;
            newtail = newtail->next;
        } else {
            newtail->next = l2;
            l2 = l2->next;
            newtail = newtail->next;
        }
    }

    if (l1) newtail->next = l1;
    if (l2) newtail->next = l2;

    ListNode* ret = newhead->next;
    free(newhead);
    newhead = NULL;
    return ret;
}

为什么最后挂尾巴不用 while？因为退出 while 循环时，至少有一个指针已经走到 NULL，剩下那条链整体是有序的，直接把剩余段的头接到 newtail 后面就完事，再写 while 反而是多余的。

五、四道题的共性

• 单链表操作的核心都是先改指针、再移动指针，顺序搞反就会出现断链或死循环。
• 凡是“新建链表”的做法，收尾都要显式把尾指针的 next 置 NULL，否则会带回原链表的残尾。
• 空链表和全删光这两种极端输入，是所有链表题的必测用例。
• 快慢指针不仅用于找中点，也用于判环（fast 追 slow），是同一套思想的两种用法。

qidao123.com企服评测-应用市场 编辑提示