链表十大经典算法题详解与实现

代码实现

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;
    
    while (curr) {
        ListNode* next = curr->next; // 暂存后继
        curr->next = prev;           // 反转指针
        prev = curr;                 // 移动 prev
        curr = next;                 // 移动 curr
    }
    return prev;
}

3. 链表的中间结点

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

思路分析 使用快慢指针法。定义 slow 和 fast 指针，初始都指向头结点。slow 每次走一步，fast 每次走两步。当 fast 到达链表末尾时，slow 恰好位于中间。注意判断条件顺序 fast && fast->next，防止空指针访问。

代码实现

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

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

题目描述 输入一个链表，输出该链表中倒数第 k 个结点。 参考：力扣 面试题 22. 链表中倒数第 k 个节点

思路分析 双指针法。让 fast 指针先向前移动 k 步，然后 fast 和 slow 同时移动。当 fast 到达末尾时，slow 正好指向倒数第 k 个结点。需额外检查 k 是否大于链表长度。

代码实现

typedef struct ListNode ListNode;
struct ListNode* getKthFromEnd(struct ListNode* head, int k) {
    ListNode* fast = head;
    ListNode* slow = head;
    
    // 先让 fast 走 k 步
    while (k--) {
        if (fast == NULL) return NULL; // 边界检查
        fast = fast->next;
    }
    
    // 同时移动
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

5. 合并两个有序链表

题目描述 将两个升序链表合并为一个新的升序链表并返回。 参考：力扣 21. 合并两个有序链表

思路分析 迭代法。创建一个虚拟头结点 dummy，用 tail 指针追踪新链表尾部。比较两个链表当前节点的值，将较小的节点接到 tail 后面。当一个链表遍历完后，直接将另一个链表的剩余部分接上即可。

代码实现

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    ListNode* tail = dummy;
    
    while (list1 && list2) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    
    // 连接剩余部分
    tail->next = (list1 ? list1 : list2);
    
    ListNode* res = dummy->next;
    free(dummy);
    return res;
}

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. 链表的回文结构

题目描述 判断一个链表是否为回文结构。 参考：力扣 234. 回文链表

思路分析 三步走策略：1）快慢指针找到中间结点；2）反转后半部分链表；3）从头结点和反转后的头结点开始比较。比较完成后建议恢复链表结构（可选）。

代码实现

typedef struct ListNode ListNode;

// 辅助函数：找中间节点
static ListNode* getMiddleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

// 辅助函数：反转链表
static ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

bool isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return true;
    
    ListNode* mid = getMiddleNode(head);
    ListNode* secondHalf = reverseList(mid);
    
    ListNode* p1 = head;
    ListNode* p2 = secondHalf;
    bool result = true;
    
    while (p2) {
        if (p1->val != p2->val) {
            result = false;
            break;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    
    // 可选：恢复链表
    // reverseList(secondHalf);
    
    return result;
}

8. 相交链表

题目描述 输入两个链表，找出它们的第一个公共结点。 参考：力扣 160. 相交链表

思路分析 计算两个链表的长度差。先遍历得到长度，对齐较长链表的指针，使两个指针距离尾部的距离相同，然后同步移动直到相遇。若不相交则同时到达 NULL。

代码实现

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (!headA || !headB) return NULL;
    
    int lenA = 0, lenB = 0;
    ListNode* pA = headA;
    ListNode* pB = headB;
    
    while (pA) { lenA++; pA = pA->next; }
    while (pB) { lenB++; pB = pB->next; }
    
    // 确保 A 是较长的链表
    if (lenA < lenB) {
        ListNode* temp = headA; headA = headB; headB = temp;
        int t = lenA; lenA = lenB; lenB = t;
    }
    
    int gap = lenA - lenB;
    while (gap--) {
        headA = headA->next;
    }
    
    while (headA && headB) {
        if (headA == headB) return headA;
        headA = headA->next;
        headB = headB->next;
    }
    
    return NULL;
}

9. 判断链表中是否有环

题目描述 给定一个链表，判断链表中是否有环。 参考：力扣 141. 环形链表

思路分析 经典的 Floyd 判圈算法。slow 每次走一步，fast 每次走两步。如果存在环，fast 最终会追上 slow；如果无环，fast 会先到达 NULL。

代码实现

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

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

题目描述 给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL。 参考：力扣 142. 环形链表 II

思路分析 基于上一题的判断有环逻辑。当快慢指针第一次相遇后，将一个指针重置到头结点，两个指针每次都走一步再次相遇，那个位置就是环的入口。数学原理是：头结点到入口的距离 = 相遇点到入口的距离。

代码实现

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            // 相遇了，开始找入口
            ListNode* ptr1 = head;
            ListNode* ptr2 = slow;
            while (ptr1 != ptr2) {
                ptr1 = ptr1->next;
                ptr2 = ptr2->next;
            }
            return ptr1;
        }
    }
    return NULL;
}

总结

链表问题的核心在于指针的灵活操作和边界条件的处理。通过上述练习，我们掌握了几个关键技巧：

1. 哨兵节点：简化了头结点删除或插入的特殊情况处理。
2. 快慢指针：解决环检测、中间节点查找的高效利器。
3. 双指针法：在合并、相交、分割等问题中能有效降低时间复杂度。
4. 原地反转：理解指针指向的变化是掌握链表反转的关键。

链表看似变化多端，实则万变不离其宗。建议在 LeetCode 上动手实践这些题目，思考不同解法的优劣，逐步构建自己的算法思维体系。数据结构的学习是一个循序渐进的过程，打好基础，方能行稳致远。