链表经典算法题详解

3. 链表的中间结点

题目描述 给定一个带有头结点的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

核心思路 快慢指针法是解决此类问题的利器。定义 slow 和 fast 指针，初始都指向头结点。slow 每次走一步，fast 每次走两步。当 fast 到达链表末尾时，slow 恰好指向中间结点。若链表长度为偶数，fast 为空时 slow 指向第二个中间结点。注意循环条件 fast && fast->next 的顺序不能更改。

参考实现

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

4. 链表中倒数第 k 个结点

题目描述 输入一个链表，输出该链表中倒数第 k 个结点。

核心思路 双指针法。定义 fast 和 slow 指针，初始都指向头结点。先让 fast 指针向前移动 k 步，然后 fast 和 slow 同时移动。当 fast 到达链表末尾时，slow 恰好指向倒数第 k 个结点。需要注意 k 大于链表长度的情况，以及空链表的判断。

参考实现

typedef struct ListNode ListNode;
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    ListNode* fast = head, *slow = head;
    if(head == NULL) return NULL;
    while(cnt--) {
        fast = fast->next;
    }
    while(fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5. 合并两个有序链表

题目描述 将两个升序链表合并为一个新的升序链表并返回。

核心思路 迭代法。创建一个虚拟头结点 dummy，用 tail 指针指向新链表的尾部。首先判断两个链表中有无空链表，若有则直接返回另一个。然后比较两个链表当前结点的值，将较小的结点接到 tail 后面，并移动对应链表的指针。当其中一个链表遍历完后，将另一个链表的剩余部分直接接上。

参考实现

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* l1 = list1, *l2 = list2;
    ListNode* newhead = NULL, *newtail = NULL;
    if(l1 == NULL) return l2;
    if(l2 == NULL) return l1;
    if(l1->val < l2->val) {
        newhead = newtail = l1; l1 = l1->next;
    } else {
        newhead = newtail = l2; l2 = l2->next;
    }
    while(l1 && l2) {
        if(l1->val < l2->val) {
            newtail->next = l1; l1 = l1->next;
        } else {
            newtail->next = l2; l2 = l2->next;
        }
        newtail = newtail->next;
    }
    if(l1) newtail->next = l1;
    if(l2) newtail->next = l2;
    return newhead;
}

6. 链表分割

题目描述 以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前，且保持原来的相对顺序。

核心思路 创建两个哑结点，分别作为小于 x 的部分和大于等于 x 的部分的头结点。遍历原链表，根据结点值的大小分别接到对应的链表后面。最后将两部分连接起来，注意要将大于等于部分链表的尾结点的 next 置空，避免形成环。记得释放哑结点内存。

参考实现

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if(head == NULL) return NULL;
    ListNode* lesshead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* lesstail = lesshead;
    ListNode* greathead = (ListNode*)malloc(sizeof(ListNode));
    ListNode* greattail = greathead;
    ListNode* pcur = head;
    while(pcur) {
        if(pcur->val < x) {
            lesstail->next = pcur;
            lesstail = lesstail->next;
        } else {
            greattail->next = pcur;
            greattail = greattail->next;
        }
        pcur = pcur->next;
    }
    greattail->next = NULL;
    lesstail->next = greathead->next;
    ListNode* ret = lesshead->next;
    free(lesshead);
    free(greathead);
    return ret;
}

7. 链表的回文结构

题目描述 判断一个链表是否为回文结构。

核心思路 三步走策略：1）使用快慢指针找到链表的中间结点；2）反转后半部分链表；3）比较前半部分和反转后的后半部分是否相同。最后最好将链表恢复原状（可选）。注意边界条件，空链表应视为回文。

参考实现

typedef struct ListNode ListNode;

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

ListNode* reverse(ListNode* middlenode) {
    ListNode* prev = NULL;
    ListNode* curr = middlenode;
    while(curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    if(head == NULL) return true;
    ListNode* reversehead = reverse(get_middlenode(head));
    ListNode* p1 = head, *p2 = reversehead;
    while(p1 && p2) {
        if(p1->val != p2->val) return false;
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}

8. 相交链表

题目描述 输入两个链表，找出它们的第一个公共结点。

核心思路 双指针法的一种变体。计算两个链表的长度差，让长链表指针先走差值步，然后两个指针同步移动，相遇点即为交点。另一种方法是两指针互相遍历对方链表，最终会在交点或 NULL 处相遇。这里采用长度差法，逻辑更直观。

参考实现

typedef struct ListNode ListNode;
#include <stdlib.h>

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    ListNode* pcur1 = headA, *pcur2 = headB;
    int count1 = 0, count2 = 0;
    while(pcur1) { pcur1 = pcur1->next; count1++; }
    while(pcur2) { pcur2 = pcur2->next; count2++; }
    
    // 检查尾节点是否相同，不同则不相交
    ListNode* tail1 = headA;
    while(tail1->next) tail1 = tail1->next;
    ListNode* tail2 = headB;
    while(tail2->next) tail2 = tail2->next;
    if(tail1 != tail2) return NULL;

    int gap = abs(count1 - count2);
    ListNode* longlist = count1 > count2 ? headA : headB;
    ListNode* shortlist = count1 > count2 ? headB : headA;
    
    while(gap--) {
        longlist = longlist->next;
    }
    while(longlist != shortlist) {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return longlist;
}

9. 判断链表中是否有环

题目描述 给定一个链表，判断链表中是否有环。

核心思路 快慢指针法。定义 slow 和 fast 指针，slow 每次走一步，fast 每次走两步。如果链表有环，则两个指针最终会在环中相遇；如果 fast 到达链表末尾（NULL），则说明链表无环。这是检测环最经典的方法。

参考实现

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* fast = head, *slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) return true;
    }
    return false;
}

10. 返回链表开始入环的第一个结点

题目描述 给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL。

核心思路 在上一题判断有环的基础上，记录快慢指针相遇点。然后让一个指针从链表头开始，另一个指针从相遇点开始，两个指针每次都走一步，它们相遇的位置就是环的入口结点。数学推导表明，从头结点到入口的距离等于从相遇点到入口的距离。

参考实现

typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode* head) {
    ListNode* fast = head, *slow = head;
    ListNode* meet = NULL;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow) {
            meet = fast;
            break;
        }
    }
    if(meet == NULL) return NULL;
    ListNode* pcur = head;
    while(pcur != meet) {
        meet = meet->next;
        pcur = pcur->next;
    }
    return meet;
}

结语

链表的核心在于指针的灵活操作和边界条件的处理。通过上述 10 道经典题目的练习，希望大家掌握了以下技巧：

• 哑结点的应用简化了头结点特殊情况的处理
• 快慢指针是解决环问题、中间结点问题的利器
• 双指针法在合并、相交等问题中表现出色
• 反转链表的迭代思路需要熟练掌握

链表的题目看似变化多端，但万变不离其宗。只要理解链表的结构特点，勤加练习，就能在面试和竞赛中游刃有余。建议在实际编码中多思考多种解法的优劣，逐步提升自己的算法思维。