链表基础与实战：单双链表实现及经典算法题解析

以下是链表的打印，具体实现如下：

1. 定义链表结构体指针指向 phead
2. 定义 pcur 等于 phead 即等于 node1
3. 若 pcur 不为 NULL，则打印当前节点的 data(存储的数据) ，并让 pcur 继续往下走
4. pcur 走到为空，跳出 while 循环，打印 NULL
5. 最后打印结果为：1->2->3->4->NULL

注意： 在这里直接使用 phead 来遍历也是一样的，重新创建 pcur 指针是为了避免由于指针指向的改变，导致无法重新找到链表的首节点。

void SLTPrint(SLTNode* phead){
    //pcur 存放的是当前节点的地址 
    SLTNode* pcur = phead;
    while(pcur){
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}

3. 申请新的节点大小空间

注意：这里要判断申请空间是否成功，如果失败退出，申请成功对 data 和 next 进行初始化。

SLTNode* SLTBuyNode(SLTDataType x){ 
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if(newnode ==NULL){
        perror("malloc fail!\n");
        exit(1);
    } 
    newnode->data = x; 
    newnode->next =NULL;
    return newnode;
}

4. 链表的尾插

向操作系统动态申请一个节点大小的空间 然后断言若传来的是 NULL，那么不能解引用，所以需要断言 pphead 不能为空，但是 *pphead 可以为空，因为它代表的是空链表，所以可以存在。这里尾插分两种情况。

链表为空：即 pphead 为空，则让 pphead 等于 newnode(为首节点) 即 1。

链表不为空：即 pphead 不为空，具体步骤如下：

1. 定义一个尾节点 ptail，初始时等于首节点 pphead
2. 遍历链表，结束条件为不能等于尾节点，注意这里结束条件是 ptail->next
3. 若为尾节点，则让尾节点 4 的 next 指针指向新节点 99

这里我们发现形参 phead 的改变没有影响到实参 plist 的改变（在传值的时候，形参的改变不影响实参 传地址：形参的改变影响实参），所以 plist 应该传地址而不是值，应为&plist，而 plist 是指针，所以 phead 要传二级指针来接受一级指针的地址，所以为 **pphead。在 if 语句中药对 pphead 解引用（*pphead=plist）为一级指针，后面也是同样的意思。

这里解释下一级指针和二级指针的概念 第一个节点 （解引用） *plist<---------->**phead(解引用两次)，左边例如 plist 是实参，右边是形参 指向第一个节点的指针 plist<-------->*phead（解引用一次后变成一级指针） 指向第一个节点的指针的地址 （取地址） &plist<---------->pphead（二级指针）

//尾插
void SLTPushBack(SLTNode**pphead, SLTDataType x){
    //如果传来的是 NULL，那么不能解引用，所以需要断言 pphead 不能为空，但是*pphead 可以为空，因为它代表的是空链表，所以可以存在
    assert(pphead);
    //*pphead 就是指向第一个节点的指针
    //空链表和非空链表两种情况 
    SLTNode* newnode = SLTBuyNode(x);
    if(*pphead ==NULL){
        *pphead = newnode;
    }else{
        SLTNode* ptail =*pphead;
        //如果 ptail 为空，那么在循环里面不可以对空指针解引用，所以会报错
        while(ptail->next){ 
            ptail = ptail->next;
        }
        //ptail 指向的就是尾节点 
        ptail->next = newnode;
    }
}

5. 链表的头插

1. 调用创建新节点的方法
2. 让新节点 9 的 next 指针指向原来的头结点 1（*pphead）
3. 让新节点 (newnode) 为新的头结点

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x){
    //空链表和非空链表都可以运行
    assert(pphead); 
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next =*pphead;
    *pphead = newnode;
}

6. 链表的尾删

代码思路如下：

1. 断言
2. 判断链表中有一个节点还是多个节点
3. 若只有一个节点（pphead->next==NULL），则直接释放，并把 *pphead 置为 NULL
4. 若有多个节点则定义 prev 和 ptail 指针指向头结点，然后遍历链表直至到尾节点，然后跳出循环，释放尾节点 ptail 并置为空，为了不让尾节点前一个节点的 next 指针为野指针，所以让 prev 为前一个节点并让其 next 指向空

注意 这里断言时：pphead（一级指针的地址）不能为空，否则不能对二级指针解引用，其次不能让链表为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个（*pphead）不能为空。

//尾删
void SLTPopBack(SLTNode** pphead ){
    //这里和头插尾差不一样，因为尾删的话，链表不能为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个*pphead 不能为空
    assert(pphead &&*pphead);
    //链表只有一个节点
    if((*pphead)->next ==NULL)//这里给*pphead 加了个括号，因为有符号的优先级，->的优先级高于*号
    {
        free(*pphead);
        *pphead =NULL;
    }else{
        //链表有多个节点 
        SLTNode* prev =*pphead;
        SLTNode* ptail =*pphead;
        while(ptail->next){ 
            prev = ptail; 
            ptail = ptail->next;
        }
        free(ptail); 
        ptail =NULL; 
        prev->next =NULL;
    }
}

7. 链表的头删

1. 定义 next 变量指向头结点的下一个节点
2. 释放头结点
3. 让 next 节点变为新的头结点

注意：这里不能直接删除 pphead，若删除找不到后面的节点 2，所以需要定义 next 保存下一个节点 2。

//头删
void SLTPopFront(SLTNode** pphead){
    //这里和尾删是一样的，解释在上面
    assert(pphead &&*pphead);
    //在这里不能直接删除第一个节点，这样就不能根据原本第一个节点的 next 指针找到原本第二个节点
    //在头删方法中，只有一个节点和多个节点如下方法都可以实现 
    SLTNode* next =(*pphead)->next;//这里也是->的优先级大于*号
    free(*pphead);
    *pphead = next;
}

8. 链表的查找

代码思路如下：

1. 定义一个变量 pcur 指向头结点
2. 循环遍历，若（if 里的语句）pcur 存储的 data 等于要查找的 x，则返回该节点
3. 否则继续往后遍历链表
4. 若循环遍历结束，没有数据等于 x，则该数据在链表中不存在

//查找 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x){ 
    SLTNode* pcur = phead;
    while(pcur){
        if(pcur->data == x){
            return pcur;
        }else{ 
            pcur = pcur->next;
        }
    }
    returnNULL;
}

9. 在指定位置之前插入数据

代码思路如下：

1. 前置条件的断言，如 pphead 和 pos 不能为空
2. 若指定位置 pos 为头结点，那么就等于是头插，直接调用头插函数即可（特殊位置）
3. 若 pos 不是头结点，定义 prev 指向头结点，遍历循环，循环条件为 prev 的 next 不等于 pos
4. prev->next 为 pos 跳出循环，将新节点的 next 指向 pos，prev 的 next 指向新节点

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){
    assert(pphead && pos);
    //当 pos 为首节点的时候，会出现对空指针解引用的操作导致下面代码报错
    //若 pos 直接等于*pphead 的时候则为头插，那么直接调用头插函数
    if(pos ==*pphead){
        SLTPushFront(pphead, x);
    }else{
        SLTNode* newnode = SLTBuyNode(x); 
        SLTNode* prev =*pphead;
        while(prev->next != pos){ 
            prev = prev->next;
        }
        newnode->next = pos; 
        prev->next = newnode;
    }
}

10. 在指定位置之后插入数据

注意：

1. 这里 (newnode->next = pos->next; pos->next = newnode) 顺序不能反过来，否则自己指向自己了
2. 这里只需 pos 和插入数据两个变量，与在指定位置之前插入数据不一样，不需要遍历找下一个节点，因为 pos 的 next 指针存储的就是下一个节点，而在指定位置之前插入数据，pos 没有保存前一个节点，需要用 pphead 遍历链表来寻找

//在指定位置之后插入数据 
void SLTInsertAfter(SLTNode* pos, SLTDataType x) { 
    assert(pos); 
    SLTNode* newnode = SLTBuyNode(x); 
    //pos newnode -> (pos->next)
    newnode->next = pos->next; 
    pos->next = newnode; 
}

11. 删除指定节点

代码思路：

1. 断言 pphead 不为空且 pos 不为空，否则怎么删除 pos 节点
2. 这里要判断特殊条件，若 pos 是头结点则直接调用已写好的头删方法
3. 否则循环遍历链表，若 prev 的 next 指向 pos，则退出循环
4. 让 prev 的 next 指向 pos 的下一个节点后再释放 pos，并把 pos 置为空

//删除 pos 结点
void SLTErase(SLTNode** pphead, SLTNode* pos){
    assert(pphead && pos);
    //要删除的节点就是头结点
    if(pos ==*pphead){
        SLTPopFront(pphead);
    }else{
        SLTNode* prev =*pphead;
        while(prev->next != pos){ 
            prev = prev->next;
        }
        //prev pos pos->next
        prev->next = pos->next; 
        free(pos); 
        pos =NULL;
    }
}

12. 删除指定节点之后的数据

在下图我们要删除 2 节点（pos->next）

1. 需要将 1 节点（pos）的 next(pos->next) 指向 3（pos->next->next）
2. 释放 2 节点（pos->next）

在上面操作中我们发现最后的 pos->next 指向 3 节点，也就是说最后释放的不是 2 而是 3 节点，所以我们需要定义 del 变量来存放 pos->next。

1. del 赋值为 pos->next，也就是 2 节点
2. 让 1 节点 (pos) 的下一个节点为 3(del->next)
3. 释放节点 2（del）并置为空

注意： 这里断言不能让 pos 指向空，也不能为尾节点，因为尾节点之后没有数据，无法删除。

//删除 pos 之后的结点
void SLTEraseAfter(SLTNode* pos){
    assert(pos && pos->next); 
    SLTNode* del = pos->next;//pos del del->next
    pos->next = del->next; 
    free(del); 
    del =NULL;
}

13. 销毁链表

不能直接释放链表，应该一个一个释放链表里面的节点，这里不能直接释放节点，应该定义 pcur 保存该节点，并且还要保存下一个节点的地址，否则要销毁下一个节点的时候找不到该节点地址，变成野指针。

代码思路如下：

1. 定义 pcur 指向头结点
2. 循环遍历链表，定义 next 并让他保存要销毁节点的下一个节点
3. 释放要销毁的节点，并让链表继续往后遍历（pcur = next）
4. 链表中所有节点都删除跳出循环，还需让 *pphead 置为空，否则它为野指针

//销毁链表
void SListDestroy(SLTNode** pphead){ 
    SLTNode* pcur =*pphead;
    while(pcur){ 
        SLTNode* next = pcur->next;
        free(pcur); 
        pcur = next;
    }
    *pphead =NULL;
}

四、单链表的思考

在数据结构学习中，链表相对于顺序表而言有以下几个优势：

1. 链表头部插入删除时间复杂度为 O(1)
2. 链表无需增容
3. 链表不存在空间浪费

五、经典链表 OJ 题

1. 移除链表元素

题目解释： 这道题题目很容易读懂，和上述我实现链表方法中的删除指定位置的节点意思类似，这里只需要给头结点就可以知道整个链表。

思路 1: 遍历链表找到值为 val 的结点，执行删除指定 pos 位置结点的操作，时间复杂度为 O(n^2)

思路 2: 创建新的链表，遍历原链表，将链表中值不为 val 的节点尾插到新链表中

1. 遍历原链表，结束条件为 pcur 为空
2. 若 pcur 存储的值不为 val 尾插到新链表中
   • 新链表为空：pcur 既是新链表的头结点也是尾节点
   • 链表不为空：尾节点的 next 指向 pcur，再让 ptail 从原来的尾节点走到 pcur 变成新的尾节点
3. 让 pcur 往后走
4. 走到空，遍历完链表跳出循环，然后一定要判断 newtail 不为空（若为空则不能解引用它的 next，其中 newtail 为空时候原链表为空），让 newtail 的 next 指向空，因为 newtail 这个节点可能存储原链表的下一个节点，在图中 5 为尾节点，但是 5 保存了 6 的地址，所以让 5 的 next 置为空

注意： 这里不能使用双指针，因为双指针法只是修改节点里面的值却没有删除节点。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){
    //创建一个空链表 
    ListNode *newhead,*newtail;
    newhead=newtail=NULL;
    //遍历原链表 
    ListNode*pcur=head;
    while(pcur){
        //找值不为 val 的结点尾插到新链表中
        if(pcur->val!=val){
            if(newhead==NULL){
                //链表为空 
                newhead=newtail=pcur;
            }else{
                //链表不为空 
                newtail->next=pcur;
                newtail=newtail->next;
            }
        }
        //遍历原链表 
        pcur=pcur->next;
    }
    if(newtail){
        newtail->next=NULL;
    }
    return newhead;
}

2. 反转链表

题目解释： 这里只需将反转链表后的头结点给返回即可，题目意思很容易理解。

思路 1： 创建新链表，遍历旧链表中的节点拿过来头插

思路 2： 创建 3 个指针，n1 初始指向空，n2 指向头节点，n3 指向头节点下一个节点，只要 n2 的节点不为空，就让 n2 的 next 指针不指向 n3，改成指向 n1。然后让 n1 走到 n2 的位置，n2 走到 n3 的位置，n3 走到下一个节点的位置。一直重复直到 n2 为空结束该过程，n1 指向的节点即为头结点。

注意： 这里有特殊情况，若链表为空直接返回头结点即可，因为 n2 为头结点，n2 为空，那么 n2->next 是错误的，不能对空指针进行解引用。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head){
    if(head==NULL){
        return head;
    } 
    ListNode*n1,*n2,*n3; 
    n1=NULL,n2=head,n3=n2->next;
    while(n2){ 
        n2->next=n1; 
        n1=n2; 
        n2=n3;
        if(n3){ 
            n3=n3->next;
        }
    }
    return n1;
}

3. 链表的中间节点

题目解释： 若链表里的节点是奇数个数，则直接返回该节点，如果节点是偶数个，那么返回第二个中间节点即可，这里题目描述很简单，但要注意节点是奇数个还是偶数个这两种情况。

思路 1： 求链表结点总数，除 2 求中间位置，返回中间位置结点 O（n）。在图 1 中，共有 5 个节点，5/2=2，定义 pcur 从 0 开始遍历，到 3 这个节点正好是下标为 2，即 3 是中间节点。

思路 2： 快慢指针，慢指针每次走一步，快指针每次走两步 即 2*慢指针=快指针。 在奇数节点个数中，若 fast->next=NULL，则不能往下走，slow 指向的节点 3 的位置就是中间节点。 在偶数节点个数中，fast=NULL 则不能往下走，slow 指向的节点 4 为中间节点。

这里判断节点是偶数个（fast=NULL）或者奇数个（fast->next=NULL）的时候，fast 和 fast->next 顺序不能相反，具体解释在代码中注释有。

注意：这里不能使用双指针向中间遍历，phead 可以向右遍历，因为存放 next 指针指向下一个节点，但是 ptail 不能往左走，因为没有存放前一个节点。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head){ 
    ListNode*slow=head; 
    ListNode*fast=head;
    while(fast&&fast->next){
        //fast 和 fast->next 位置不能换，如果先 fast-> next，fast 都已经为空了，不能对空解引用
        //代码会报错，只要第一个为假，就不会判断 fast->next 为真为假 
        slow=slow->next; 
        fast=fast->next->next;
    }
    return slow;
}

4. 合并两个有序链表

题目解释： 题目给我们两个排好的升序链表，将他们连在一起合并成一个新的升序链表。

思路：

1. 定义 l1 指向第一个链表，l2 指向第二个链表，定义一个新链表
2. 循环遍历链表 1 和 2，谁的值小放入新链表中，结束条件为：l1 和 l2 其中一个走到为空就退出循环
3. l1 小则将 l1 数据插入到新链表中，若新链表是为空，则插入进来的 l1 既事头结点也是尾节点，若链表不为空，则让为节点的下一个节点指向 l1，newtail 走到 l1 位置，同理 l2 也是如此
4. 跳出循环，只有两种情况，l1 走到空，l2 走到空，不可能有 l1 和 l2 均为空的情况，因为若 l1 和 12 存放的数据相等时，我们随机让 l1 或者 l2 走往后走，走到为空。
5. 若 l1 不为空，则让 newtail 的 next 指向 l1，同理 l2 也是如此。

以上思路看起来是不是理所当然，但是当我们调试代码的时候报错了，下面的报错是不是很熟悉呀，我们根据他给的示例带入我们上述思路跑一下，l1 为空无法进入循环，直接跳到思路 5 中，新链表为空，其尾节点为空，不能对空进行解引用，我们的代码却让新节点的 newtail 的 next 指向 l2，所以报错。

我们根据上面问题发现是没有对链表为空进行处理，所以我们在思路 1 后面直接进行判断，若 l1 为空，直接返回 l2，同理 l2 也是如此。

在下面写代码时候我们发现思路中的步骤 3 判断链表是否为空，代码重复度过高，我们可以创建非空链表（malloc 节点大小空间，别忘记最后要释放哦），则不需要进行判空号，直接尾插。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ 
    ListNode*l1=list1; 
    ListNode*l2=list2;
    if(list1==NULL){
        return list2;
    }
    if(list2==NULL){
        return list1;
    }
    //新链表 
    ListNode*newhead,*newtail; 
    newhead=newtail=NULL;
    while(l1&&l2){
        if(l1->val<l2->val){
            //l1 插入到新链表中
            if(newhead==NULL){
                //链表为空 
                newhead=newtail=l1;
            }else{
                newtail->next=l1; 
                newtail=newtail->next;
            } 
            l1=l1->next;
        }else{
            //l2 插入到新链表中
            if(newhead==NULL){ 
                newhead=newtail=l2;
            }else{
                newtail->next=l2; 
                newtail=newtail->next;
            } 
            l2=l2->next;
        }
    }
    //跳出循环，只有两种情况，l1 走到空，l2 走到空
    //有没有可能 l1l2 同时为空？不可能
    if(l1){ 
        newtail->next=l1;
    }
    if(l2){ 
        newtail->next=l2;
    }
    return newhead;
}

5. 相交链表

题目解释： 如果两个链表相交则是相交链表，这里解释下啥是相交链表，若 l1 的某个节点和 l2 的某个节点相同，即是相交节点，有三种情况 l1 和 l2 的头结点就相同，l1 和 l2 中间有节点相同，l2 和 l3 的尾节点相同。

注意大家可能疑惑有没有 l1 和 l2 链表相交成'x'字型，答案是否定的，若交叉点为 n1，n1 的 next 节点只能存放一个地址，而不是多个，若两个链表相交，则从交叉点开始后面的节点均相同。

思路： 这里需要解决两个问题，1.如何判断链表是否相交 2.找相交的起始节点。

试错：一个个比较链表节点的 next 是否相等，这个方法仅限相交之前的节点个数相等（长度相同），所以该方法不行。

问题 1： 看尾节点的地址是否相同

问题 2： 找长度差，也就是找大小链表（求出两个链表的长度差），大链表先走长度差次，然后再一起比较两个链表的 next 是否相同。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* getIntersectionNode(struct ListNode*headA, struct ListNode*headB){
    //求出两个链表的长度 
    ListNode*pa=headA,*pb=headB;
    int sizeA=0,sizeB=0;
    while(pa){
        ++sizeA; 
        pa=pa->next;
    }
    while(pb){
        ++sizeB; 
        pb=pb->next;
    }
    int gap=abs(sizeA-sizeB);//abs:求绝对值的函数
    //让长链表先走 gap 步 
    ListNode*shortlist=headA; 
    ListNode*longlist=headB;
    if(sizeA>sizeB){ 
        longlist=headA; 
        shortlist=headB;
    }
    while(gap--){ 
        longlist=longlist->next;
    }
    //shortlist longlist 在同一起跑线
    while(shortlist){
        if(shortlist==longlist){
            return shortlist;
        } 
        shortlist=shortlist->next; 
        longlist=longlist->next;
    }
    returnNULL;
}

6. 环形链表

题目解释： 链表带环如上图一样，它具有尾节点的 next 指向不为空的性质，若链表带环则返回 true 否则返回 false。

思路： 快慢指针（慢指针每次走一步，快指针每次走两步）：在环内追逐，若链表带环，快慢指针会相遇。

证明： 这里大家如果感兴趣可以自己证明或者在网上搜下为啥在环形链表中使用快慢指针，最终两指针会相遇！

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode*head){ 
    ListNode*slow=head,*fast=head;
    while(fast&&fast->next){ 
        slow=slow->next; 
        fast =fast->next->next;
        if(slow==fast){
            //相遇
            return true;
        }
    }
    return false;
}

7. 环形链表 II

题目解释： 这与上题类似，不过多解释。

思路： 这里还是快慢指针，但是要注意的是这里有个结论：相遇点到入环起始结点的距离等于链表头结点到入环起始结点的距离。

这里大家也可以自己证明下该结论如何成立的。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* detectCycle(struct ListNode*head){ 
    ListNode*slow=head,*fast=head;
    while(fast&&fast->next){ 
        slow=slow->next; 
        fast=fast->next->next;
        if(fast==slow){
            //相遇点 
            ListNode*pcur=head;
            while(slow!=pcur ){ 
                slow=slow->next; 
                pcur=pcur->next;
            }
            return pcur;
        }
    }
    returnNULL;
}

8. 随机链表的复制

题目解释： 这道题提到我们要对这个链表进行深拷贝，这里我们要拷贝原链表中所有的数据，拷贝到一个全新的链表，即复制的链表中的指针不能指向原链表，藕断丝连。（该链表与普通节点不同的是额外添加了指针，该指针可以指向链表中的任何节点或空节点）

深拷贝：定义 pcur 指针指向当前节点，再来一个指针 pcur2 指向另外一个节点，但是该节点存储的值和前面一个节点存储的值相同，但是节点的地址互不相同（如图 1），简单理解就是把链表从一个地方拿到别的地方，链表里面存放到值完全一样，就是链表的位置即地址不一样而已。

浅拷贝：定义 pcur 指针指向当前节点，再来一个指针 pcur2 也指向该节点，它们使用的是同一块地址即浅拷贝（如图 2）。

代码思路： 这里大家可能想到把链表中除了 random 指针其他全部复制过来，然后再遍历原链表设置新链表的 random 指针，这个想法是正确的，但是我们发现置 random 指针很麻烦，无法处理。

思路 2：

1. 拷贝节点：在原链表上申请新的节点 pcur，让它遍历原链表并不断创建和它当前位置节点一模一样的节点，然后让创建的这个节点尾插到该位置的后面（这里暂时只需改变 next 指向即可），依次重复该操作直至 pcur 走到空为止，链表拷贝完成。
2. 置 random 指针：在复制链表中定义 copy 指针和 pcur 一起遍历新旧链表，让 copy->random=pcur->random->next。
3. 断开新旧链表：pcur 和 copy 同时遍历新旧链表，让 copy->next 不再指向 pcur，而是指向 pcur->next，依次重复执行直至 copy 走到空，那么新旧链表已断开。

注意：若链表为空需要特殊处理，直接返回即可。

代码实现：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
//创建新节点 
Node*buyNode(int x){ 
    Node*node=(Node*)malloc(sizeof(Node)); 
    node->val=x; 
    node->next=node->random=NULL;
    return node;
}
void AddNode(Node*head){ 
    Node*pcur=head;
    while(pcur){ 
        Node*next=pcur->next;
        //创建新节点，插入到 pcur 结点之后 
        Node*newnode=buyNode(pcur->val); 
        newnode->next=pcur->next; 
        pcur->next=newnode; 
        pcur=next;
    }
}
void setRandom(Node*head){ 
    Node*pcur=head;
    while(pcur){ 
        Node*copy=pcur->next;
        if(pcur->random){ 
            copy->random=pcur->random->next;
        } 
        pcur=copy->next;
    }
}
struct Node* copyRandomList(struct Node* head){
    if(head==NULL){
        return head;
    }
    //1. 拷贝结点 
    AddNode(head);
    //2. 置 random 指针
    setRandom(head);
    //3 断开链表 
    Node*pcur=head; 
    Node*newHead,*newTail; 
    newHead=newTail=pcur->next;
    while(newTail->next){ 
        pcur=newTail->next; 
        newTail->next=pcur->next; 
        newTail=newTail->next;
    }
    return newHead;
}

六、单链表与双链表源码

单链表源码

SList.h 源码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//定义节点的结构
typedef int SLTDataType;
typedef struct SListNode {
    SLTDataType data;
    struct SListNode* next;
} SLTNode;
void SLTPrint(SLTNode* phead);
//尾插
void SLTPushBack(SLTNode**pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找 
SLTNode* SLTFind(SLTNode* pphead, SLTDataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode*pos , SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除 pos 之后的节点
void SLTEraseAfter(SLTNode* pos);
//顺序表的销毁
void SListDestroy(SLTNode**pphead);

SList.c 源码

#include"SList.h"
void SLTPrint(SLTNode* phead){
    //pcur 存放的是当前节点的地址 
    SLTNode* pcur = phead;
    while(pcur){
        printf("%d->", pcur->data);
        pcur = pcur->next;
    }
    printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x){ 
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if(newnode ==NULL){
        perror("malloc fail!\n");
        exit(1);
    } 
    newnode->data = x; 
    newnode->next =NULL;
    return newnode;
}
//尾插
void SLTPushBack(SLTNode**pphead, SLTDataType x){
    //如果传来的是 NULL，那么不能解引用，所以需要断言 pphead 不能为空，但是*pphead 可以为空，因为它代表的是空链表，所以可以存在
    assert(pphead);
    //*pphead 就是指向第一个节点的指针
    //空链表和非空链表两种情况 
    SLTNode* newnode = SLTBuyNode(x);
    if(*pphead ==NULL){
        *pphead = newnode;
    }else{
        SLTNode* ptail =*pphead;
        //如果 ptail 为空，那么在循环里面不可以对空指针解引用，所以会报错
        while(ptail->next){ 
            ptail = ptail->next;
        }
        //ptail 指向的就是尾节点 
        ptail->next = newnode;
    }
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x){
    //空链表和非空链表都可以运行
    assert(pphead); 
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next =*pphead;
    *pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead ){
    //这里和头插尾差不一样，因为尾删的话，链表不能为空，总不能删空吧，这不可能的，所以和头插尾插不同的是添加了个*pphead 不能为空
    assert(pphead &&*pphead);
    //链表只有一个节点
    if((*pphead)->next ==NULL)//这里给*pphead 加了个括号，因为有符号的优先级，->的优先级高于*号
    {
        free(*pphead);
        *pphead =NULL;
    }else{
        //链表有多个节点 
        SLTNode* prev =*pphead;
        SLTNode* ptail =*pphead;
        while(ptail->next){ 
            prev = ptail; 
            ptail = ptail->next;
        }
        free(ptail); 
        ptail =NULL; 
        prev->next =NULL;
    }
}
//头删
void SLTPopFront(SLTNode** pphead){
    //这里和尾删是一样的，解释在上面
    assert(pphead &&*pphead);
    //在这里不能直接删除第一个节点，这样就不能根据原本第一个节点的 next 指针找到原本第二个节点
    //在头删方法中，只有一个节点和多个节点如下方法都可以实现 
    SLTNode* next =(*pphead)->next;//这里也是->的优先级大于*号
    free(*pphead);
    *pphead = next;
}
//查找 
SLTNode* SLTFind(SLTNode* phead, SLTDataType x){ 
    SLTNode* pcur = phead;
    while(pcur){
        if(pcur->data == x){
            return pcur;
        }else{ 
            pcur = pcur->next;
        }
    }
    returnNULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x){
    assert(pphead && pos);
    //当 pos 为首节点的时候，会出现对空指针解引用的操作导致下面代码报错
    //若 pos 直接等于*pphead 的时候则为头插，那么直接调用头插函数
    if(pos ==*pphead){
        SLTPushFront(pphead, x);
    }else{
        assert(pphead &&*pphead);
        assert(pos); 
        SLTNode* newnode = SLTBuyNode(x); 
        SLTNode* prev =*pphead;
        while(prev->next != pos){ 
            prev = prev->next;
        }
        newnode->next = pos; 
        prev->next = newnode;
    }
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//为啥没有头结点？？？
{
    assert(pos); 
    SLTNode* newnode = SLTBuyNode(x);
    newnode->next = pos->next; 
    pos->next = newnode;
}
//删除 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos){
    assert(pphead &&*pphead);
    assert(pos);
    //pos 是头结点，那么可以直接调用头删代码
    if(pos ==*pphead){
        SLTPopFront(pphead);
        //测试过只能是 pphead 不能是*pphead
    }else{
        SLTNode* prev =*pphead;
        while(prev->next != pos){ 
            prev = prev->next;
        }
        prev->next = pos->next; 
        free(pos); 
        pos =NULL;
    }
}
//删除 pos 之后的节点
void SLTEraseAfter(SLTNode* pos){
    assert(pos&&pos->next);
    //这里注意 pos 的 next 也不能为空，不然怎么删除 
    SLTNode* del = pos->next; 
    pos->next = del->next; 
    free(del); 
    del =NULL;
    //注意不能这样写：pos->next=pos->next->next
    //free(pos)
    //pos->next=NULL;
    //因为这样写就是把 pos 后的节点的下一个节点也释放掉了
}
//顺序表的销毁
void SListDestroy(SLTNode**pphead){
    assert(pphead &&*pphead); 
    SLTNode* pcur =*pphead;
    while(pcur){ 
        SLTNode* next = pcur->next;
        free(pcur); 
        pcur = next;
    }
    //pcur 为空
    *pphead =NULL;
}

test.c

#include"SList.h"
void test(){
    //手动构造一个链表 
    SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode)); 
    SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode)); 
    SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode)); 
    SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode)); 
    node1->data = 1; 
    node2->data = 2; 
    node3->data = 3; 
    node4->data = 4; 
    node1->next = node2; 
    node2->next = node3; 
    node3->next = node4; 
    node4->next =NULL; 
    SLTNode* plist = node1;
    SLTPrint(plist);
}
void test01(){ 
    SLTNode* plist =NULL;
    SLTPushBack(&plist,1);
    SLTPushBack(&plist,2);
    SLTPushBack(&plist,3);
    SLTPushBack(&plist,4);
    SLTPrint(plist);
    //SLTPushFront(&plist, 1);
    //SLTPushFront(&plist, 2);
    //SLTPushFront(&plist, 3);
    //SLTPushFront(&plist, 4);
    //SLTPrint(plist);
    //SLTPopBack(&plist);
    //SLTPrint(plist);
    //SLTPopBack(&plist);
    //SLTPrint(plist);
    //SLTPopBack(&plist);
    //SLTPrint(plist);
    //SLTPopBack(&plist);
    //SLTPrint(plist);
    ////SLTPopFront(&plist);
    //SLTPrint(plist);
    //SLTPopFront(&plist);
    //SLTPrint(plist);
    //SLTPopFront(&plist);
    //SLTPrint(plist);
    //SLTPopFront(&plist);
    //SLTPrint(plist);
    //SLTPopFront(&plist);
    //SLTPrint(plist);
    SLTNode* find = SLTFind(plist,4);
    //if (find == NULL)
    //{
    // printf("未找到！\n");
    //}
    //else
    //{
    // printf("找到了！\n");
    //}
    //SLTInsert(&plist, find, 88);
    //1 88 2 3 4
    //SLTInsertAfter(find, 88);
    //1 2 88 3 4
    //SLTErase(&plist, find);
    //SLTEraseAfter(find);
    //1 3 4
    SListDestroy(&plist);
    SLTPrint(plist);
}
struct ListNode{
    int val;//data
    struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val){ 
    ListNode* newHead,* newTail; 
    newHead = newTail =NULL; 
    ListNode* pcur = head;
    while(pcur){
        //找值不为 val 的结点尾插到新链表中
        if(pcur->val != val){
            //尾插
            if(newHead ==NULL){
                //链表为空 
                newHead = newTail = pcur;
            }else{
                //链表不为空 
                newTail->next = pcur; 
                newTail = newTail->next;
            }
        } 
        pcur = pcur->next;
    }
    return newHead;
}
void test02(){ 
    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode* node5 = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode* node6 = (ListNode*)malloc(sizeof(ListNode)); 
    ListNode* node7 = (ListNode*)malloc(sizeof(ListNode)); 
    node1->val = 1; 
    node2->val = 2; 
    node3->val = 6; 
    node4->val = 3; 
    node5->val = 4; 
    node6->val = 5; 
    node7->val = 6; 
    node1->next = node2; 
    node2->next = node3; 
    node3->next = node4; 
    node4->next = node5; 
    node5->next = node6; 
    node6->next = node7; 
    node7->next =NULL; 
    ListNode* plist = node1;
    removeElements(plist,6);
}
int main(){
    //test();
    //test01();
    test02();
    return 0;
}

双链表源码

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDatatype;
//定义双向链表（结点）结构
typedef struct ListNode {
    LTDatatype data;
    struct ListNode* next;
    struct ListNode* prev;
} LTNode;
//初始化 
LTNode* LTInit();
//void LTDesTroy(LTNode** pphead);
//接口一致性，传一级，在函数调用结束后需要手动将实参置为 NULL
void LTDesTroy(LTNode* phead);
//void LTInit(LTNode** pphead);
void LTPrint(LTNode* phead); 
bool LTEmpty(LTNode* phead);
//尾插
//phead 节点不会发生改变，参数就为一级
//phead 节点发生改变，参数就为二级
void LTPushBack(LTNode* phead, LTDatatype x);
void LTPushFront(LTNode* phead, LTDatatype x);
//尾删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//在 pos 位置之后插入数据----pos 位置之前插入代码基本是一样的（双向的）--课下可以实现以下在 pos 之前插入
void LTInsert(LTNode* pos, LTDatatype x);
void LTErase(LTNode* pos); 
LTNode* LTFind(LTNode* phead, LTDatatype x);

List.c

#include"List.h"
LTNode* buyNode(LTDatatype x){ 
    LTNode* node = (LTNode*)malloc(sizeof(LTNode)); 
    node->data = x; 
    node->next = node->prev = node;
    return node;
}
LTNode* LTInit(){
    //创建头结点
    //LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
    //phead->data = -1;
    //phead->next = phead->prev = phead;
    LTNode* phead = buyNode(-1);
    return phead;
}
//void LTInit(LTNode** pphead)
//{
// assert(pphead);
// *pphead = (LTNode*)malloc(sizeof(LTNode));
// (*pphead)->data = -1;
// (*pphead)->next = (*pphead)->prev = *pphead;
//}
//void LTDesTroy(LTNode** pphead)
//{
// LTNode* pcur = (*pphead)->next;
// while (pcur != *pphead)
// {
// LTNode* next = pcur->next;
// free(pcur);
// pcur = next;
// }
// free(*pphead);
// *pphead = NULL;
//}
void LTDesTroy(LTNode* phead){ 
    LTNode* pcur = phead->next;
    while(pcur != phead){ 
        LTNode* next = pcur->next;
        free(pcur); 
        pcur = next;
    }
    free(phead); 
    phead =NULL;
}
void LTPushBack(LTNode* phead, LTDatatype x){
    assert(phead); 
    LTNode* newnode = buyNode(x);
    //phead phead->prev newnode newnode->prev = phead->prev; 
    newnode->next = phead; 
    phead->prev->next = newnode; 
    phead->prev = newnode;
}
void LTPushFront(LTNode* phead, LTDatatype x){
    assert(phead); 
    LTNode* newnode = buyNode(x);
    //phead newnode phead->next newnode->next = phead->next; 
    newnode->prev = phead; 
    phead->next->prev = newnode; 
    phead->next = newnode;
}
void LTPrint(LTNode* phead){ 
    LTNode* pcur = phead->next;
    while(pcur != phead){
        printf("%d -> ", pcur->data); 
        pcur = pcur->next;
    }
    printf("\n");
}
bool LTEmpty(LTNode* phead){
    assert(phead);
    return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead){
    assert(!LTEmpty(phead)); 
    LTNode* del = phead->prev;
    //phead del->prev del
    del->prev->next = phead; 
    phead->prev = del->prev; 
    free(del); 
    del =NULL;
}
void LTPopFront(LTNode* phead){
    assert(!LTEmpty(phead)); 
    LTNode* del = phead->next;
    //phead del del->next
    del->next->prev = phead; 
    phead->next = del->next; 
    free(del); 
    del =NULL;
}
LTNode* LTFind(LTNode* phead, LTDatatype x){ 
    LTNode* pcur = phead->next;
    while(pcur != phead){
        if(pcur->data == x){
            return pcur;
        } 
        pcur = pcur->next;
    }
    returnNULL;
}
//在 pos 位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x){
    assert(pos); 
    LTNode* newnode = buyNode(x);
    //pos newnode pos->next
    newnode->next = pos->next; 
    newnode->prev = pos; 
    pos->next->prev = newnode; 
    pos->next = newnode;
}
void LTErase(LTNode* pos){
    assert(pos);
    //pos->prev pos pos->next
    pos->prev->next = pos->next; 
    pos->next->prev = pos->prev; 
    free(pos); 
    pos =NULL;
}

test.c

#include"List.h"
void test(){
    //LTNode* plist = NULL;
    //LTInit(&plist); 
    LTNode* plist = LTInit();
    LTPushBack(plist,1);
    LTPushBack(plist,2);
    LTPushBack(plist,3);
    LTPushBack(plist,4);
    //LTPushFront(plist, 1);
    //LTPushFront(plist, 2);
    //LTPushFront(plist, 3);
    //LTPushFront(plist, 4);
    LTPrint(plist);
    //4 3 2 1
    ////LTPopBack(plist);
    //LTPrint(plist);
    //LTPopBack(plist);
    //LTPrint(plist);
    //LTPopBack(plist);
    //LTPrint(plist);
    //LTPopBack(plist);
    //LTPrint(plist);
    ////LTPopFront(plist);
    //LTPrint(plist);
    //LTPopFront(plist);
    //LTPrint(plist);
    //LTPopFront(plist);
    //LTPrint(plist);
    //LTPopFront(plist);
    //LTPrint(plist);
    //LTPopFront(plist);
    //LTPrint(plist);
    //LTNode* find = LTFind(plist, 3);
    //if (find == NULL)
    //{
    // printf("ûҵ\n");
    //}
    //else {
    // printf("ҵˣ\n");
    //}
    //LTInsert(find, 99);
    //LTErase(find);
    //LTPrint(plist);
    LTDesTroy(plist); 
    plist =NULL;
}
int main(){
    test();
    return 0;
}

总结

链表作为数据结构中的重要线性结构，其灵活的存储方式和高效的插入删除操作使其在众多场景中不可或缺。本文从链表的基本概念入手，详细解析了链表的分类方式，通过手动实现单链表的各项核心操作，深入剖析了指针操作的细节与边界条件的处理，尤其对二级指针的使用场景和原理进行了重点说明。

在此基础上，通过对比顺序表，凸显了链表在头部操作、空间利用等方面的优势，并结合 8 道经典 OJ 题，展示了链表在实际问题中的应用技巧，如快慢指针、新链表构建、环形链表特性利用等。最后提供的单链表和双链表完整源码，为实践练习提供了直接参考。

掌握链表不仅是理解更复杂数据结构（如哈希表、树、图）的基础，其指针操作逻辑也能显著提升对内存管理和程序设计的理解。希望本文能帮助读者扎实掌握链表知识，为后续数据结构学习和算法提升奠定坚实基础。