链表经典 OJ 题目解析与 C 语言实现 | 极客日志

C算法

链表经典 OJ 题目解析与 C 语言实现

链表十大经典 OJ 题目涵盖删除节点、反转链表、寻找中间结点、倒数第 k 个结点、合并有序链表、链表分割、回文结构判断、相交链表检测、环检测及入环节点查找。内容提供思路分析与 C 语言代码实现，涉及快慢指针、哑结点、双指针等核心技巧，帮助读者掌握链表操作基础与面试考点。

SqlMaster发布于 2026/3/22更新于 2026/4/210 浏览

链表经典 OJ 题目解析与 C 语言实现

引言

链表是一种基础且重要的数据结构，在程序设计中有着广泛的应用。由于其物理存储的非连续性，链表在插入、删除操作上具有独特的优势，但也给某些操作（如随机访问）带来了挑战。在技术面试和算法竞赛中，链表相关的题目出现频率极高，熟练掌握链表的常见操作和经典问题的解法，是每个程序员必备的技能。本文精选了 10 道经典的链表 OJ 题目，从思路分析到 C 语言代码实现，逐步详解，并穿插了快慢指针、哑结点等常用技巧的讲解。

1. 删除链表中等于给定值 val 的所有结点

题目描述 删除链表中所有值为 val 的结点，返回删除后的链表头结点。力扣 203. 移除链表元素

思路分析 创建一个带哨兵位的新链表，将符合条件的节点接到新链表后面，然后返回哨兵位的 next 节点，注意尾节点的 next 需要置为 NULL，如果原链表是空链表，那么直接返回空链表。

代码实现

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    if(head==NULL) {
        return NULL;
    }
    ListNode* newhead,* newtail;
    newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur=head;
    while(pcur) {
        if(pcur->val!=val) {
            newtail->next=pcur;
            newtail=newtail->next;
        }
        pcur=pcur->next;
    }
    newtail->next=NULL;
    return newhead->next;
}

2. 反转一个单链表

题目描述 反转一个单链表，返回反转后的链表头结点。力扣 206. 反转链表

思路分析 迭代法：使用三个指针 prev、curr、next。初始时 prev 为 NULL，curr 指向头结点。每次将 curr->next 指向 prev，然后三个指针整体后移，直到 curr 为 NULL，此时 prev 即为新头结点。

代码实现

更多推荐文章

相关免费在线工具

加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online
Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online
Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online
HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online
JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    ListNode* n1,*n2,*n3;
    if(head==NULL) return head;
    n1=NULL,n2=head,n3=head->next;
    while(n2) {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3) n3=n3->next;
    }
    return n1;
}

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

typedef struct ListNode ListNode;
struct ListNode* trainingPlan(struct ListNode* head, int k) {
    ListNode* fast=head,* slow=head;
    if(head==NULL) return NULL;
    while(k--) {
        fast=fast->next;
    }
    while(fast) {
        fast=fast->next;
        slow=slow->next;
    }
    return slow;
}

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 = l1->next; // l1 后移
        } else {
            newtail->next = l2; // 将 l2 节点挂到尾部
            l2 = l2->next; // l2 后移
        }
        newtail = newtail->next; // newtail 移动到新节点
    }
    if (l1) newtail->next = l1;
    if (l2) newtail->next = l2;
    return newhead;
}

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

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

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

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

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