链表十大经典 OJ 题目详解与实战技巧

3. 链表的中间结点

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

思路与实现 快慢指针法是解决此类问题的利器。定义两个指针 slow 和 fast，初始都指向头结点。slow 每次走一步，fast 每次走两步。当 fast 到达链表末尾时，slow 恰好指向中间结点。若链表长度为偶数，fast 为空时 slow 指向第二个中间结点。

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 个结点。（参考：力扣 面试题 22. 链表中倒数第 k 个节点）

思路与实现 双指针法。定义两个指针 fast 和 slow，初始都指向头结点。先让 fast 指针向前移动 k 步，然后 fast 和 slow 同时移动。当 fast 到达链表末尾时，slow 恰好指向倒数第 k 个结点。需要注意 k 大于链表长度的情况，此时应提前返回 NULL。

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;
        if (!fast && cnt > 0) return NULL; // 防止越界
    }
    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) {
    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 的结点之前，且保持原来的相对顺序。（参考：力扣 86. 分割链表）

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

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL) return NULL;
    ListNode* lesshead, *lesstail;
    ListNode* greathead, *greattail;
    lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
    greathead = greattail = (ListNode*)malloc(sizeof(ListNode));
    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;
// 找到中间节点
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. 相交链表

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

思路与实现 双指针法。这里采用计算长度差的方法。先遍历两个链表获取长度，判断尾结点是否相同（不同则不相交）。计算长度差，让长链表指针先走差值步，然后两指针同步移动，相遇点即为交点。

typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    ListNode* pcur1 = headA, *pcur2 = headB;
    int count1 = 0, count2 = 0;
    while (pcur1->next) { pcur1 = pcur1->next; count1++; }
    while (pcur2->next) { pcur2 = pcur2->next; count2++; }
    if (pcur1 != pcur2) return NULL;
    int gap = count1 > count2 ? count1 - count2 : count2 - count1;
    ListNode* longlist = headA, *shortlist = headB;
    if (count2 > count1) { longlist = headB; shortlist = headA; }
    while (gap--) longlist = longlist->next;
    while (longlist != shortlist) {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return longlist;
}

9. 判断链表中是否有环

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

思路与实现 快慢指针法。定义 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。（参考：力扣 142. 环形链表 II）

思路与实现 在上一题判断有环的基础上，记录快慢指针相遇点。然后让一个指针从链表头开始，另一个指针从相遇点开始，两个指针每次都走一步，它们相遇的位置就是环的入口结点。数学推导可证明：设头结点到环入口距离为 L，环入口到相遇点距离为 X，环长度为 R，则有 L = nR - X。

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

总结

通过以上十道经典题目的练习，相信大家已经掌握了链表操作的基本技巧：

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

链表的题目看似变化多端，但万变不离其宗。只要理解链表的结构特点，勤加练习，就能在面试和竞赛中游刃有余。建议读者在 LeetCode 上将这些题目逐个 AC，并在解题过程中思考多种解法的优劣，逐步提升自己的算法思维。