【下篇】链表 OJ 题，原来可以这样 “盘”！

用户11872857

发布于 2025-12-17 15:52:50

190

📚 初阶数据结构

🚀 个人主页：< 脏脏a-CSDN博客 >

📊 文章专栏：< 数据结构 >

🔗 上篇回顾：<【上篇】链表OJ题 >

📋 其他专栏：< C++ > 、< 数据结构 > 、< 优选算法 >

CM11链表分割

OR36链表的回文序列

160. 相交链表

141. 环形链表

【问题1】：slow 走 1 步，fast 走 2 步，他们是否会相遇？会不会错过？

【问题2】：slow 走 1 步，fast 走 n 步（n ≥ 3），他们是否会相遇？会不会错过？

142. 环形链表II

CM11链表分割

【题目链接】：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

【算法原理】：

创建两个新链表，一个尾差值大于等于x的节点，一个尾插值小于x的节点，最后让大链表尾差到小链表后面

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)
    { 
        // 定义并初始化"小于x"的链表的哨兵节点和尾指针
        ListNode* lesshead, *lesstail;
        lesshead = new ListNode(0);  // 哨兵节点（简化头节点处理）
        lesstail = lesshead;         // 尾指针初始指向哨兵节点

        // 定义并初始化"大于等于x"的链表的哨兵节点和尾指针
        ListNode* greathead, *greattail;
        greathead = new ListNode(0);  // 哨兵节点
        greattail = greathead;        // 尾指针初始指向哨兵节点
        
        ListNode* cur = pHead;  // 遍历原链表的指针

        // 遍历原链表，将节点分到两个链表中
        while (cur) 
        {
            if (cur->val >= x) 
            {
                // 当前节点大于等于x，加入"大于等于x"的链表
                greattail->next = cur;
                greattail = greattail->next;  // 尾指针后移
            } 
            else 
            {
                // 当前节点小于x，加入"小于x"的链表
                lesstail->next = cur;
                lesstail = lesstail->next;    // 尾指针后移
            }
            cur = cur->next;  // 继续遍历下一个节点
        }

        // 拼接两个链表："小于x"的链表尾部连接"大于等于x"的链表的真实头节点（跳过哨兵）
        lesstail->next = greathead->next;
        // 处理"大于等于x"的链表尾部，避免形成环（原链表最后节点可能指向其他节点）
        greattail->next = nullptr;

        // 新链表的头节点是"小于x"的链表的真实头节点（跳过哨兵）
        pHead = lesshead->next;
        
        // 释放两个哨兵节点的内存，避免泄漏
        delete lesshead;
        delete greathead;
        
        return pHead;  // 返回分区后的链表头节点
    }
};

OR36链表的回文序列

【题目链接】：https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

【算法原理】：

1、找到中间节点

2、从中间节点开始，对后半段逆置

3、前半段和后半段比较，如果相等，说明是回文结构

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class PalindromeList {
public:
    // 辅助函数：查找链表的中间节点（用于分割链表）
    ListNode* mid(ListNode* head)
    {
        ListNode* fast, *slow;
        fast = slow = head;  // 快慢指针均从表头出发

        // 快指针走2步，慢指针走1步，快指针到尾时，慢指针指向中间
        while (fast && fast->next) 
        {
            fast = fast->next->next;  // 快指针每次移动2步
            slow = slow->next;        // 慢指针每次移动1步
        }

        return slow;  // 返回中间节点（偶数节点时返回后半段第一个节点）
    }

    // 辅助函数：反转链表（用于反转后半段链表）
    ListNode* reverse(ListNode* head)
    {
        ListNode* n1, *n2, *n3;
        n1 = nullptr;       // 指向反转后前一个节点（初始为空）
        n2 = head;          // 指向当前需要反转的节点
        if (n2) n3 = head->next;  // 保存当前节点的下一个节点（避免断链）
        else n3 = nullptr;

        // 遍历并反转链表
        while (n2) 
        {
            n2->next = n1;  // 反转当前节点指向（指向n1）
            
            // 三个指针依次后移
            n1 = n2;
            n2 = n3;
            if (n3) 
              n3 = n3->next;  // 若n3不为空则继续后移
        }

        return n1;  // 反转后n1为新表头
    }

    // 主函数：判断链表是否为回文结构
    bool chkPalindrome(ListNode* A) 
    {
        // 1. 找到链表中间节点
        ListNode* midnode = mid(A);
        // 2. 反转中间节点之后的后半段链表
        ListNode* rhead = reverse(midnode);
        
        // 3. 同时遍历原链表前半段和反转后的后半段，比较节点值
        while (rhead && A) 
        {
            if (rhead->val != A->val) 
            {
                return false;  // 值不相等，不是回文
            }
            rhead = rhead->next;  // 移动到反转链表的下一个节点
            A = A->next;          // 移动到原链表的下一个节点
        }

        // 所有比较的节点值都相等，是回文
        return true;
    }
};

160. 相交链表

【题目链接】：https://leetcode.cn/problems/intersection-of-two-linked-lists/

【算法原理】：

先分别算出两个链表的长度，让长的走差距步，在同时走，如果遇到两个地址相等的节点，那么该节点就是相交节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int lenA = 0;  // 存储链表A的长度
        int lenB = 0;  // 存储链表B的长度

        ListNode* curA = headA;  // 遍历链表A的指针，命名更规范
        ListNode* curB = headB;  // 遍历链表B的指针，命名更规范

        // 计算链表A的长度
        while (curA) {
            curA = curA->next;
            lenA++;
        }

        // 计算链表B的长度
        while (curB) {
            curB = curB->next;
            lenB++;
        }

        // 若两链表的尾节点不同，说明一定不相交（相交链表尾节点必相同）
        if (curA != curB) {
            return NULL;
        }

        // 计算两链表长度差
        int gap = abs(lenA - lenB);
        
        // 初始化长短链表头指针（默认A为短，B为长，后续根据实际长度调整）
        ListNode* shortHead = headA;  // 短链表头指针，命名更规范
        ListNode* longHead = headB;   // 长链表头指针，命名更规范

        // 若A更长，则交换长短指针
        if (lenA > lenB) {
            shortHead = headB;
            longHead = headA;
        }

        // 让长链表指针先移动gap步，使两指针到尾节点的距离相等
        while (gap--) {
            longHead = longHead->next;
        }

        // 两指针同步移动，直到相遇（相遇点即为相交节点）
        while (longHead != shortHead) {
            longHead = longHead->next;
            shortHead = shortHead->next;
        }

        // 返回相交节点（若不相交，此时两指针均为null，也符合返回要求）
        return longHead;
    }
};

141. 环形链表

【题目链接】：https://leetcode.cn/problems/linked-list-cycle/

【算法原理】：

创建两个指针，一个一次走一步，一个一次走两步，如果有环，并且两者都入环了，那么，每走一次，他两之间的距离缩小1，就演变成了一个追击问题了，最终两者之间的距离为0时就追上了，也就代表有环，如果fast为空了，代表没环

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        // 定义快慢指针，初始都指向链表头节点
        ListNode* fast = head;  // 快指针：每次移动2步
        ListNode* slow = head;  // 慢指针：每次移动1步

        // 循环条件：快指针及其下一个节点均不为空（避免空指针解引用）
        while (fast && fast->next) 
        {
            fast = fast->next->next;  // 快指针移动2步
            slow = slow->next;        // 慢指针移动1步

            // 若快慢指针相遇，说明链表有环（环内追上）
            if (slow == fast) 
            {
                return true;
            }
        }

        // 若循环退出，说明快指针走到了链表末尾（无环）
        return false;
    }
};

【问题1】：slow 走 1 步，fast 走 2 步，他们是否会相遇？会不会错过？

【问题2】：slow 走 1 步，fast 走 `n` 步（`n ≥ 3`），他们是否会相遇？会不会错过？

142. 环形链表II

【题目链接】：https://leetcode.cn/problems/linked-list-cycle-ii/

【算法原理】：

【思路1】：

结论：一个指针从相遇点走，一个指针从起始点走，会在入口点相遇

推导过程：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        // 定义快慢指针，初始均指向链表头节点
        ListNode* slow;
        ListNode* fast;
        slow = fast = head;

        // 遍历链表，快指针每次走2步，慢指针每次走1步
        while (fast && fast->next) {
            fast = fast->next->next;  // 快指针移动2步
            slow = slow->next;        // 慢指针移动1步

            // 若快慢指针相遇，说明链表有环，开始找环入口
            if (fast == slow) {
                ListNode* meet = slow;  // 记录相遇点
                ListNode* start = head; // 从链表起点开始

                // 相遇点指针和起点指针同步移动，直到相遇（相遇点即为环入口）
                while (meet != start) {
                    meet = meet->next;   // 相遇点指针后移1步
                    start = start->next; // 起点指针后移1步
                }

                return meet;  // 返回环入口节点
            }
        }

        // 若循环退出，说明链表无环，返回null
        return NULL;
    }
};

【思路2】：相遇点跟相遇点的下一个节点直接链接断开，找入口点，转换成找链表交点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {

        // 步骤1：用快慢指针找相遇点
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* meetPoint = nullptr;
        while (fast && fast->next) 
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) 
            {
                meetPoint = slow;
                break;
            }
        }
        if (meetPoint == nullptr)// 无环
        { 
            return nullptr;
        }

        // 步骤2：断开相遇点的环，将问题转换为找两个链表的交点
        ListNode* cycleNext = meetPoint->next;
        meetPoint->next = nullptr; // 断开环

        // 现在问题变为：找head和cycleNext两个链表的交点（即原环入口）
        ListNode* p1 = head;
        ListNode* p2 = cycleNext;
        // 先计算两个链表的长度
        int len1 = 0, len2 = 0;
        ListNode* cur1 = p1;
        ListNode* cur2 = p2;
        while (cur1) 
        {
            len1++;
            cur1 = cur1->next;
        }
        while (cur2)
        {
            len2++;
            cur2 = cur2->next;
        }

        // 让长链表先走长度差步
        int gap = abs(len1 - len2);
        cur1 = p1;
        cur2 = p2;
        if (len1 > len2) 
        {
            while (gap--) 
            {
                cur1 = cur1->next;
            }
        } 
        else 
        {
            while (gap--) 
            {
                cur2 = cur2->next;
            }
        }

        // 同步遍历找交点（原环入口）
        while (cur1 != cur2) 
        {
            cur1 = cur1->next;
            cur2 = cur2->next;
        }

        
        return cur1;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-16，如有侵权请联系 cloudcommunity@tencent.com 删除

算法