链表OJ题

六道链表 OJ 题：思路、代码与坑

链表是面试高频区，六道题基本覆盖所有套路：快慢指针（中点、倒数第 k、判环）、双指针归位（相交）、原地反转（回文）、三步穿插（随机链表复制）。先说总纲：

• 单链表不能反向遍历，所以「从后往前」的问题一律转成「找中点 / 反转」。
• 双指针的核心不是写法，是让两个指针走出确定的长度差——长度差就是你要的解。
• 所有操作优先用原地 O(1) 空间，别上来就建数组。

下面代码都补齐了头文件和结构体定义，可直接编译。

一、链表的回文结构

1.1 思路

单链表不能从后往前走，那就先找中间节点 → 反转后半段 → 两路逐一比较。注意奇偶数：middleNode 用快慢指针让 slow 停在后半段的第一个节点（长度偶数时取偏右的那个），这样比较不会漏位也不会重复。

1.2 代码

#include <stdio.h>
#include <stdbool.h>

typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 找中点：slow 最终停在后半段起点（偶数长度时偏右）
struct ListNode* middleNode(struct ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// 反转链表（迭代，n1 为新头）
struct ListNode* reverseList(struct ListNode* head) {
    if (NULL == head) return head;
    ListNode *n1 = NULL, *n2 = head, *n3 = head->next;
    while (n2) {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3) n3 = n3->next;
    }
    return n1;
}

bool chkPalindrome(ListNode* A) {
    ListNode *mid  = middleNode(A);
    ListNode *rmid = reverseList(mid);
    while (A && rmid) {
        if (A->val != rmid->val) return false;
        A    = A->next;
        rmid = rmid->next;
    }
    return true;
}

1.3 坑

• reverseList 里 n3 = n3->next 必须在改 n2->next 之前先把 next 存下来，否则链一断就再也找不到后继。
• 比较完不还原链表也能通过 OJ，但工程代码建议还原（存一下 mid 和原顺序），否则调用方拿到的是逆序的链表。
• 时间复杂度 O(n)（走三遍仍是 O(n)），空间 O(1)——这是最优解，用栈做是 O(n) 空间，会被扣分。

二、相交链表

2.1 思路

两个链表相交则尾节点必然相同。先分别走到尾，尾不同直接不相交；尾相同就用长度差对齐：长的先走 gap 步，然后同步走，首次相等即交点。

2.2 代码

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode *curA = headA, *curB = headB;
    int lenA = 0;
    while (curA->next) { ++lenA; curA = curA->next; }

    int lenB = 0;
    while (curB->next) { ++lenB; curB = curB->next; }

    if (curA != curB) return NULL;          // 尾不同，不相交

    int gap = abs(lenA - lenB);
    struct ListNode *longList = headA, *shortList = headB;
    if (lenB > lenA) { longList = headB; shortList = headA; }

    while (gap--) longList = longList->next;   // 长的先走 gap 步

    while (longList != shortList) {            // 同步走找交点
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}

2.3 更巧的一行写法

不需要算长度，两个指针各走完自己那条链再走对方的，第二次相遇点就是交点（走的总路程都等于 A+B 两段长度）：

if (!headA || !headB) return NULL;
struct ListNode *a = headA, *b = headB;
while (a != b) {
    a = a ? a->next : headB;
    b = b ? b->next : headA;
}
return a;   // 不相交时最后会在 NULL 相遇

这写法省掉一次遍历，面试时作为「优化思路」说出来加分。

三、链表中倒数第 k 个结点

3.1 思路（快慢指针）

让 fast 先走 k 步，然后 slow 与 fast 同步走，fast 到空时 slow 正好在倒数第 k 个。关键细节：fast 要走到空（不是尾），写法上是「先走 k 步再判断」，判断放在循环体内。

3.2 代码

#include <stdio.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    struct ListNode *slow = pListHead, *fast = pListHead;

    while (k--) {
        // k 还没减到 0，链表已经空了 —— k 大于链表长度
        if (NULL == fast) return NULL;
        fast = fast->next;
    }

    while (fast) {          // fast 走到空，slow 就是倒数第 k 个
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

易错点：如果写成先判 fast == NULL 再走 k 步、且循环走 k+1 次，结果会偏一个。k 非法（≤0）时也要 return NULL，多数 OJ 不单独测，但工程上必须处理。

四、环形链表（判断有没有环）

#include <stdio.h>
#include <stdbool.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

bool hasCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;      // 相遇 = 有环
    }
    return false;                           // fast 到尾或 NULL = 无环
}

原理：快指针每轮走 2 步、慢指针 1 步，有环就一定会追上（相对速度 1），无环则 fast 先到 NULL。别把循环条件写成只看 slow —— fast->next->next 要先保证 fast 和 fast->next 非空，判空顺序反了会野指针。

五、环形链表 II（找入环点）

5.1 法一：一次相遇公式（推荐）

设头到环入口距离 a、环入口到相遇点距离 b、环长 c，则 fast 走 (a+b)+m·c，slow 走 (a+b)。因 fast 速度是 slow 2 倍：2(a+b) = a+b+m·c → a = m·c − b。意思是「从头走 a」等价于「从相遇点沿环走 a」——两路同速，第一次相遇就是环入口。

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            struct ListNode* meet = slow;
            while (meet != head) {          // 两路同速走，相遇即入口
                meet = meet->next;
                head = head->next;
            }
            return meet;
        }
    }
    return NULL;
}

5.2 法二：拆链转相交问题

相遇点处把链表从 meet 断开，就变成「head 和 meet->next 两条链求交点」，复用第二题的 getIntersectionNode：

#include <stdlib.h>   // abs

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            struct ListNode *meet = slow;
            struct ListNode *headx = meet->next;
            meet->next = NULL;             // 断开成两条链
            return getIntersectionNode(head, headx);
        }
    }
    return NULL;
}

法二会改坏原链表结构，OJ 能过但工程上不推荐；法一无副作用，记这一个就够。

六、随机链表的复制

6.1 难点

每个节点多一个 random 指针，指向随机的任意节点或 NULL。不能直接「先复制值再连 random」——原节点的 random 指向的是原节点，得先建立新旧节点的映射。

6.2 三步穿插法（O(1) 空间）

1. 复制节点并插到原节点后面：A→B→C 变成 A→A'→B→B'→C→C'。
2. 设置 random：复制节点的 random = 原 random 的 next（因为 next 位置就是它对应的复制体）。
3. 拆开：把混合链表拆成原链和复制链，尾插法。

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int val;
    struct Node *next;
    struct Node *random;
};

struct Node* copyRandomList(struct Node* head) {
    struct Node *cur = head;

    // 1. 拷贝节点插入原节点后面
    while (cur) {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;      // 插入
        cur->next = copy;
        cur = cur->next->next;       // 迭代
    }

    // 2. 控制拷贝节点的 random
    cur = head;
    while (cur) {
        struct Node* copy = cur->next;
        copy->random = (cur->random) ? cur->random->next : NULL;
        cur = cur->next->next;
    }

    // 3. 拆链：原链还原，复制链接好
    struct Node *copyhead = NULL, *tail = NULL;
    cur = head;
    while (cur) {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if (NULL == tail) copyhead = tail = copy;   // 尾插
        else { tail->next = copy; tail = tail->next; }
        cur->next = next;                           // 还原原链
        cur = next;
    }
    return copyhead;
}

6.3 两个坑

• 用哈希表也能做（Node* → Node* 映射），空间 O(n)，写法直白；三步法是 O(1) 空间的标准解，面试优先答三步法。
• 拆链时务必先存 next（代码里的 next = copy->next），否则改完 cur->next 就断了，cur = cur->next->next 会直接崩。
• 手写 malloc 记得检查返回值，别在 OJ 里裸写不管（虽然 OJ 不判）。

小结

六道题的能力地图：

题目	核心手法	时间	空间
回文	快慢指针找中点 + 反转后半段	O(n)	O(1)
相交	判尾 + 长度差对齐（或双路走一遍）	O(m+n)	O(1)
倒数第 k	fast 先走 k 步	O(n)	O(1)
判环	slow 1 步 / fast 2 步，相遇即成环	O(n)	O(1)
找入环点	相遇后两路同速，首遇即入口	O(n)	O(1)
随机链表复制	插入复制体 → 串 random → 拆链	O(n)	O(1)

一句话心法：「差一步」用快慢指针，「位置对齐」用长度差，「反向」用反转，「找不到映射」就先插一个副本进去。

qidao123.com企服评测-应用市场 编辑提示