链表经典 OJ 题目实战解析

3. 链表的中间结点

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

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

代码实现

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 个结点。

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

代码实现

typedef struct ListNode ListNode;
struct ListNode* trainingPlan(struct ListNode* head, int cnt) {
    if(head == NULL) return NULL;
    ListNode* fast = head;
    ListNode* slow = head;
    // 确保 k 不超过链表长度，实际 OJ 通常保证合法，此处做防御性编程
    while(cnt--) {
        if(fast == NULL) return NULL;
        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;
    ListNode* l2 = list2;
    ListNode* newhead = NULL;
    ListNode* 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;

// 找到中间节点
static ListNode* get_middlenode(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

// 翻转链表
static 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;
    ListNode* p2 = reversehead;
    while(p1 && p2) {
        if(p1->val != p2->val) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}

8. 相交链表

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

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

代码实现

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if(headA == NULL || headB == NULL) return NULL;
    ListNode* pcur1 = headA;
    ListNode* pcur2 = headB;
    while(pcur1 != pcur2) {
        pcur1 = pcur1 ? pcur1->next : headB;
        pcur2 = pcur2 ? pcur2->next : headA;
    }
    return pcur1;
}

9. 判断链表中是否有环

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

思路分析 快慢指针法。定义 slow 和 fast 指针，slow 每次走一步，fast 每次走两步。如果链表有环，则两个指针最终会在环中相遇；如果 fast 到达链表末尾（NULL），则说明链表无环。

代码实现

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

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

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

思路分析 在上一题判断有环的基础上，记录快慢指针相遇点。然后让一个指针从链表头开始，另一个指针从相遇点开始，两个指针每次都走一步，它们相遇的位置就是环的入口结点。数学推导表明，头结点到环入口距离 L 与环入口到相遇点距离 X 满足特定关系，使得两指针同步移动必在入口相遇。

代码实现

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* fast = head;
    ListNode* 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) {
        pcur = pcur->next;
        meet = meet->next;
    }
    return meet;
}

结语

链表的核心在于指针的灵活操作和边界条件的处理。通过上述十道经典题目的练习，可以熟练掌握哑结点简化头结点处理、快慢指针解决环问题、双指针法处理合并与相交等技巧。链表题目看似变化多端，但万变不离其宗，理解结构特点并勤加练习，定能在面试和竞赛中游刃有余。