链表经典 OJ 题目详解与代码实现

3. 链表的中间结点

题目描述

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。力扣 876. 链表的中间结点

思路分析

快慢指针法：定义两个指针 slow 和 fast，初始都指向头结点。slow 每次走一步，fast 每次走两步。当 fast 到达链表末尾时，slow 恰好指向中间结点。若链表长度为偶数，fast 为空时 slow 指向第二个中间结点。

代码实现

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow,*fast;
    slow=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 大于链表长度的情况。

代码实现

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. 合并两个有序链表

题目描述

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。力扣 21. 合并两个有序链表

思路分析

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

代码实现

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    // 处理空链表情况
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    // 确定第一个节点（初始化 newhead 和 newtail）
    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,* 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 false;
    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. 相交链表

思路分析

双指针法：创建两个指针 pA 和 pB，分别指向两个链表的头结点。两个指针同时移动，当 pA 到达链表末尾时，重定向到链表 B 的头结点；当 pB 到达链表末尾时，重定向到链表 A 的头结点。最终两个指针会在相交结点相遇（若无相交，则同时指向 NULL）。

代码实现

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=abs(count1-count2);
    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（n 为快指针在环中绕的圈数）。

代码实现

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;
            fast=NULL;
        }
    }
    if(meet==NULL) return NULL;
    ListNode* pcur=head;
    while(pcur!=meet) {
        meet=meet->next;
        pcur=pcur->next;
    }
    return meet;
}

结语

链表作为数据结构的基础，其核心在于指针的灵活操作和边界条件的处理。通过以上 10 道经典题目的练习，相信大家已经掌握了链表操作的基本技巧：

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

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