链表经典 OJ 题目详解

前言

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

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

题目描述 删除链表中所有值为 val 的结点，返回删除后的链表头结点。

思路分析 创建一个带哨兵位的新链表，将符合条件的节点接到新链表后面，然后返回哨兵位的 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. 反转一个单链表

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

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

代码实现

typedef struct ListNode ListNode;
 ListNode*  {
    ListNode* n1,*n2,*n3;
    (head==)  head;
    n1=,n2=head,n3=head->next;
    (n2) {
        n2->next=n1;
        n1=n2;
        n2=n3;
        (n3) n3=n3->next;
    }
     n1;
}