数据结构·一篇搞定链表（含面试题）！

嗨喽，好久不见，甚是想念，肖恩偷懒了，上周没更新，你们听我狡辩…先祝大家五一快乐啊
那么本节我们就来康康链表

一. 链表简介

A. 什么是链表？

链表是一种动态集合，每个元素都是一个独立的对象，称为节点（Node）。每个节点包含两个部分：数据域和指针域。数据域存储实际数据，而指针域则存储指向下一个节点的地址。这种结构允许链表动态地增长或缩小，并且可以高效地插入、删除和遍历元素。

// 定义链表节点结构体  
typedef struct Node {  
    int data;  
    struct Node* next;  
} Node;
1
2
3
4
5

B. 链表的类型（单向链表、双向链表、循环链表）

链表有多种类型，包括：

• 单向链表（Singly Linked List）：每个节点只有一个指针域，指向下一个节点。
• 双向链表（Doubly Linked List）：每个节点有两个指针域，一个指向前一个节点，另一个指向下一个节点。

typedef int LTDataType;
typedef struct ListNode
{
 struct ListNode* next; //指针保存下⼀个节点的地址
 struct ListNode* prev; //指针保存前⼀个节点的地址
 LTDataType data;
}LTNode;
1
2
3
4
5
6
7

• 循环链表（Circular Linked List）：最后一个节点的指针域指向第一个节点，形成一个环形结构。

C. 链表的优缺点

链表具有以下优点：

• 高效地插入、删除和遍历元素
• 动态地增长或缩小
• 节省内存空间

然而，链表也存在一些缺点：

• 访问元素需要遍历整个链表
• 插入、删除操作可能会导致链表重新排列
• 需要更多的内存空间来存储指针域

二. 链表的基本操作

// 创建新节点  
Node* createNode(int data) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    if (newNode == NULL) {  
        exit(1); // 内存分配失败，退出程序  
    }  
    newNode->data = data;  
    newNode->next = NULL;  
    return newNode;  
}  
1
2
3
4
5
6
7
8
9
10

A. 插入

1. 在开头插入

// 在开头插入节点  
void insertAtBeginning(Node** head, int data) {  
    Node* newNode = createNode(data);  
    newNode->next = *head;  
    *head = newNode;  
}  
1
2
3
4
5
6

2. 在末尾插入

// 在末尾插入节点  
void insertAtEnd(Node** head, int data) {  
    Node* newNode = createNode(data);  
    if (*head == NULL) {  
        *head = newNode;  
        return;  
    }  
    Node* current = *head;  
    while (current->next != NULL) {  
        current = current->next;  
    }  
    current->next = newNode;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 在特定位置插入

// 在特定位置插入节点（位置从0开始）  
void insertAtPosition(Node** head, int position, int data) {  
    if (position < 0) {  
        return; // 无效的位置  
    }  
    Node* newNode = createNode(data);  
    if (position == 0) {  
        newNode->next = *head;  
        *head = newNode;  
        return;  
    }  
    Node* current = *head;  
    int count = 0;  
    while (current != NULL && count < position - 1) {  
        current = current->next;  
        count++;  
    }  
    if (current == NULL) {  
        return; // 超出链表长度  
    }  
    newNode->next = current->next;  
    current->next = newNode;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

B. 删除

1. 删除第一个节点

// 删除第一个节点  
void deleteFirstNode(Node** head) {  
    if (*head == NULL) {  
        return; // 链表为空  
    }  
    Node* temp = *head;  
    *head = (*head)->next;  
    free(temp);  
}  
1
2
3
4
5
6
7
8
9

2. 删除最后一个节点

// 删除最后一个节点  
void deleteLastNode(Node** head) {  
    if (*head == NULL || (*head)->next == NULL) {  
        free(*head);  
        *head = NULL;  
        return; // 链表为空或只有一个节点  
    }  
    Node* current = *head;  
    Node* prev = NULL;  
    while (current->next != NULL) {  
        prev = current;  
        current = current->next;  
    }  
    prev->next = NULL;  
    free(current);  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 删除特定节点 （查找）

// 删除特定节点（通过值查找）  
void deleteNode(Node** head, int key) {  
    if (*head == NULL) {  
        return; // 链表为空  
    }  
    if ((*head)->data == key) {  
        Node* temp = *head;  
        *head = (*head)->next;  
        free(temp);  
        return;  
    }  
    Node* current = *head;  
    while (current->next != NULL && current->next->data != key) {  
        current = current->next;  
    }  
    if (current->next != NULL) {  
        Node* temp = current->next;  
        current->next = current->next->next;  
        free(temp);  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 检查链表是否为空：

如果链表为空（*head == NULL），函数直接返回，因为没有任何节点可以删除。

• 删除头节点：

如果头节点的数据等于key，则更新头指针以跳过这个节点，并释放原头节点的内存。
这一步确保了如果头节点是需要删除的节点，它可以被正确地删除。

• 遍历链表以找到要删除的节点：

使用current指针遍历链表，直到找到值为key的节点或者到达链表的末尾。
这里有一个潜在的问题：如果链表中存在多个值为key的节点，函数只会删除第一个找到的节点。
如果在遍历过程中current->next->data等于key，则找到了要删除的节点。但是，注意这里current指向的是要删除节点的前一个节点。
如果current->next是NULL，说明已经到达链表末尾且没有找到值为key的节点，因此不需要进行任何操作。
如果找到了要删除的节点（即current->next不为NULL且current->next->data等于key），则通过更新current->next来跳过这个节点，并释放该节点的内存。

• 注意事项：

如果链表中没有节点或者没有值为key的节点，函数将不会执行任何内存释放操作，这是正确的。
函数假设链表中的节点值是唯一的，或者只删除第一个找到的值为key的节点。如果需要删除所有值为key的节点，则需要修改循环逻辑。

//（通过位置查找）
void deleteNodeAtPosition(Node** head, int position) {  
    if (*head == NULL || position < 0) {  
        return; // 链表为空或者位置无效  
    }  
      
    // 如果要删除的是头节点  
    if (position == 0) {  
        Node* temp = *head;  
        *head = (*head)->next;  
        free(temp);  
        return;  
    }  
  
    Node* current = *head;  
    int count = 0;  
    // 找到要删除节点的前一个节点  
    while (current->next != NULL && count < position - 1) {  
        current = current->next;  
        count++;  
    }  
  
    // 如果位置超出了链表长度  
    if (current == NULL || current->next == NULL) {  
        return;  
    }  
  
    Node* temp = current->next;  
    current->next = temp->next;  
    free(temp);  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

在这个函数中，我们首先处理头节点的特殊情况（位置为0）。然后，我们使用一个current指针遍历链表，同时用一个count变量来跟踪当前遍历到的位置。当我们到达要删除节点的前一个节点时，我们更新current->next来跳过要删除的节点，并释放要删除节点的内存。

请注意，如果尝试删除的位置超出了链表的长度（即位置大于链表的节点数），这个函数什么都不会做。

C. 遍历

遍历的逻辑也比较简单，大家绝对看得懂，我在这里就不做分析啦

1. 迭代遍历

// 迭代遍历链表  
void iterativeTraversal(Node* head) {  
    Node* current = head;  
    while (current != NULL) {  
        printf("%d ", current->data);  
        current = current->next;  
    }  
    printf("\n");  
} 
1
2
3
4
5
6
7
8
9

2. 递归遍历

// 递归遍历链表  
void recursiveTraversal(Node* head) {  
    if (head == NULL) {  
        return;  
    }  
    printf("%d ", head->data);  
    recursiveTraversal(head->next);  
}  
1
2
3
4
5
6
7
8

三. 链表的其它操作（OJ题）

A. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。OJ链接

struct ListNode {
      int val;
      struct ListNode *next;
 };
1
2
3
4

迭代方式

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL) {
        return head;
    }   
    struct 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1. 如果输入的头节点head为空（即链表为空），则直接返回空指针。
2. 定义三个指针n1、n2和n3，分别表示当前节点、下一个节点和下下个节点。初始化时，n1为空，n2指向头节点head，n3指向n2的下一个节点。
3. 进入循环，遍历链表：
   将当前节点n2的指针指向前一个节点n1，实现反转。
   更新n1为当前节点n2，n2为下一个节点n3，n3为下下个节点。
   如果下一个节点n3不为空，则将n3更新为下下个节点。
4. 循环结束后，返回反转后的链表头节点n1。

递归方式

struct ListNode* reverseList(struct ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    struct ListNode *reversed_head = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return reversed_head;
1
2
3
4
5
6
7
8

1. 如果输入的头节点head为空或者头节点的下一个节点为空（即链表只有一个节点或为空），则直接返回头节点。
2. 调用递归函数reverseList，传入头节点的下一个节点head->next，得到反转后的链表头节点reversed_head。
3. 将原头节点head的下一个节点的下一个节点指向当前头节点head，实现反转操作。
4. 将当前头节点head的下一个节点指向空，表示当前头节点成为新的尾节点。 返回反转后的链表头节点reversed_head。

B. 链表的中间结点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
OJ链接
我们完全可以遍历两遍来完成这个题，but，两遍时间复杂度有点高，方法太笨，那还有其它方法吗，当然有，look下面

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode *p1, *p2;
    p1 = p2 = head;
    if (head == NULL)
        return head;
    while (p2 && p2->next) {
        p1 = p1->next;
        p2 = p2->next->next;
    }
    return p1;
}
1
2
3
4
5
6
7
8
9
10
11

1. 定义两个指针p1和p2，初始时均指向头节点head。
2. 如果头节点head为空，则直接返回空指针。
3. 进入循环，同时移动指针p1和p2，其中p1每次向后移动一个节点，p2每次向后移动两个节点。
4. 当p2或p2->next为空时，循环结束，此时p1指向链表的中间节点。
5. 返回中间节点p1。

通过快慢指针的方法，实现了寻找链表中间节点的功能。快指针每次移动两步，慢指针每次移动一步，当快指针到达链表尾部时，慢指针刚好指向链表的中间节点。这种方法在遍历一次链表的情况下就可以找到中间节点，时间复杂度为O(n)。

C. 合并两个链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。OJ链接

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode dummy;
    struct ListNode* tail = &dummy;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        } 
        tail = tail->next;
    }
    
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }
    
    return dummy.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1. 定义一个虚拟头节点dummy和一个尾节点指针tail，初始时尾节点指向虚拟头节点。
2. 进入循环，当两个有序链表均不为空时： 比较两个链表头节点的值，将值较小的节点接在尾节点后面，同时更新尾节点指针和对应链表的头节点。
3. 如果其中一个链表还有剩余节点，将剩余节点直接接在尾节点后面。
4. 返回虚拟头节点的下一个节点，即合并后的有序链表的头节点。

四. 链表面试题

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

OJ链接

struct ListNode* removeElements(struct ListNode* head, int val) {
        struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* cur = dummy;
    
    while (cur->next != NULL) {
        if (cur->next->val == val) {
            struct ListNode* temp = cur->next;
            cur->next = cur->next->next;
            free(temp);
        } else {
            cur = cur->next;
        }
    }
    return dummy->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1. 定义一个虚拟头节点dummy，并将其指向链表头节点head。
2. 定义一个指针cur指向虚拟头节点，用于遍历链表。
3. 进入循环，当当前节点的下一个节点不为空时：
   如果当前节点的下一个节点的值等于目标值val，则删除该节点：将当前节点的下一个节点保存在临时指针temp中，然后将当前节点的next指针指向下下一个节点，并释放temp指向的节点。
   如果当前节点的下一个节点的值不等于目标值val，则继续向后移动当前节点。
4. 遍历结束后，返回虚拟头节点的下一个节点，即删除指定数值节点后的链表头节点。

2. 倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。 OJ链接
这个和上面那个中间结点有异曲同工之妙
依旧是双指针，我就不步步解释了

int kthToLast(struct ListNode* head, int k){
    struct ListNode *pre = head, *cur = head;
    for (int i = 0; i < k; i++)
        cur = cur->next;
    while (cur != NULL) {
        pre = pre->next;
        cur = cur->next;
    }
    return pre->val;
}
1
2
3
4
5
6
7
8
9
10

3. 分割链表

编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。OJ链接

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head==NULL)
        return head;
    ListNode*minhead,*mintail;
    ListNode*maxhead,*maxtail;
    minhead=mintail=(ListNode*)malloc(sizeof(ListNode));
    maxhead=maxtail=(ListNode*)malloc(sizeof(ListNode));
    ListNode*pucr=head;
    while(pucr){
        if((pucr->val)<x){
            mintail->next=pucr;
            mintail=mintail->next;
        }else{
            maxtail->next=pucr;
            maxtail=maxtail->next;
        }    
        pucr=pucr->next;
    }   
    maxtail->next=NULL;
    mintail->next=maxhead->next;
    ListNode*ret;
    ret=minhead->next;
    free(minhead);
    free(maxhead);
    minhead=maxhead=NULL;
    return ret;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

函数的逻辑如下：

1. 首先判断链表是否为空，若为空则直接返回头节点指针。
2. 定义四个指针minhead、mintail、maxhead和maxtail，分别表示小于x的节点部分的头指针、尾指针，大于等于x的节点部分的头指针、尾指针。
3. 分配内存并初始化minhead和mintail指向一个新节点，maxhead和maxtail也同理。
4. 使用指针pucr遍历整个链表：
   • 如果当前节点的值小于x，则将其接在小于x部分的尾部，并更新mintail指针。
   • 如果当前节点的值大于等于x，则将其接在大于等于x部分的尾部，并更新maxtail指针。
5. 遍历结束后，将maxtail指向的节点的next指针设为NULL，连接小于x部分和大于等于x部分。
6. 释放minhead和maxhead指向的节点，避免内存泄漏。
7. 返回重新排列后的链表头节点指针。

这段代码通过遍历链表，将小于给定值的节点和大于等于给定值的节点分别连接到两个新的链表中，最后将两个链表连接起来，实现了将链表重新排列的功能。时间复杂度为O(n)，其中n为链表的长度。

4. 链表的回文结构

OJ链接
不用在意是C++的结构，C++兼容C的，大家主要看逻辑

class PalindromeList {
  public:
    bool chkPalindrome(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return true;
        }

        // 找到链表中点
        ListNode* slow = head, *fast = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        // 反转后半部分链表
        ListNode* prev = nullptr, *curr = slow->next, *next;
        while (curr != nullptr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        // 比较前半部分和反转后的后半部分链表
        ListNode* p1 = head, *p2 = prev;
        while (p2 != nullptr) {
            if (p1->val != p2->val) {
                return false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        return true;
    }
};  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

函数的逻辑如下：

1. 首先判断链表是否为空或只有一个节点，如果是，则直接返回true，因为空链表或只有一个节点的链表都可以视为回文链表。
2. 使用快慢指针法找到链表的中点，慢指针slow每次移动一个节点，快指针fast每次移动两个节点，当快指针到达链表末尾时，慢指针指向链表中点。
3. 反转链表的后半部分：定义指针prev指向空，指针curr指向慢指针的下一个节点，然后进行链表反转操作，将curr指向的节点逐个插入到prev之前。
4. 比较前半部分和反转后的后半部分链表：定义两个指针p1和p2分别指向链表头和反转后的后半部分链表头，逐个比较节点的值，如果不相等，则返回false。
5. 如果所有节点的值都相等，则返回true，表示链表是回文链表。

5. 相交链表

输入两个链表，找出它们的第一个公共结点。OJ链接

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *pA = headA;
    struct ListNode *pB = headB;
    
    while (pA != pB) {
        pA = pA ? pA->next : headB;
        pB = pB ? pB->next : headA;
    }
    
    return pA;
}
1
2
3
4
5
6
7
8
9
10
11

函数的逻辑如下：

1. 定义两个指针pA和pB分别指向链表headA和headB的头节点。
2. 进入循环，判断pA和pB是否相等，如果相等则表示找到了交点，直接返回该节点。
3. 如果pA不为空，则将pA移动到下一个节点；如果pA为空，则将pA指向链表headB的头节点，这样可以保证两个指针走过的距离相同。
4. 同样地，如果pB不为空，则将pB移动到下一个节点；如果pB为空，则将pB指向链表headA的头节点。
5. 继续循环直到找到交点或者两个指针同时到达链表末尾。
6. 返回交点指针或NULL。

6. 环形链表1

给你一个链表的头节点 head ，判断链表中是否有环.

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况.

如果链表中存在环 ，则返回 true 。 否则，返回 false .
OJ链表

// 判断链表是否有环  
bool hasCycle(ListNode *head) {  
    if (head == NULL || head->next == NULL) {  
        // 空链表或只有一个节点的链表不可能有环  
        return false;  
    }  
  
    ListNode *slow = head;  
    ListNode *fast = head->next;  
  
    // 快慢指针开始移动，直到它们相遇或快指针到达链表尾部  
    while (slow != fast) {  
        // 如果快指针到达链表尾部，说明没有环  
        if (fast == NULL || fast->next == NULL) {  
            return false;  
        }  
        slow = slow->next; // 慢指针每次移动一个节点  
        fast = fast->next->next; // 快指针每次移动两个节点  
    }  
  
    // 如果快慢指针相遇，说明有环  
    return true;  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

详细讲解放在下一期

7. 环形链表2

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null.

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况.

不允许修改链表。
OJ链表

typedef struct ListNode {  
    int val;  
    struct ListNode *next;  
} ListNode;  
  
// 函数声明  
ListNode *detectCycle(ListNode *head);  
  
ListNode *detectCycle(ListNode *head) {  
    if (!head || !head->next) {  
        // 空链表或只有一个节点的链表没有环  
        return NULL;  
    }  
  
    ListNode *slow = head;  
    ListNode *fast = head;  
  
    // 第一步：检测环是否存在  
    while (fast && fast->next) {  
        slow = slow->next;  
        fast = fast->next->next;  
  
        // 如果快慢指针相遇，说明有环  
        if (slow == fast) {  
            break;  
        }  
    }  
  
    // 如果fast或fast->next为NULL，说明没有环  
    if (!fast || !fast->next) {  
        return NULL;  
    }  
  
    // 第二步：找到环的起始节点  
    slow = head;  
    while (slow != fast) {  
        slow = slow->next;  
        fast = fast->next;  
    }  
  
    // slow（或fast）现在指向环的起始节点  
    return slow;  
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

详细讲解同样放在下一期

8. 随机链表的复制

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。OJ链接

// 链表节点的定义  
typedef struct Node {  
    int val;  
    struct Node *next;  
    struct Node *random;  
} Node;  
  
// 创建一个新节点  
Node* createNewNode(int val) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    if (!newNode) return NULL;  
    newNode->val = val;  
    newNode->next = NULL;  
    newNode->random = NULL;  
    return newNode;  
}  
  
// 深拷贝链表  
Node* copyRandomList(Node* head) {  
    if (!head) return NULL;  
  
    // 第一步：复制节点并插入到原节点后面  
    Node* curr = head;  
    while (curr) {  
        Node* copy = createNewNode(curr->val);  
        copy->next = curr->next;  
        curr->next = copy;  
        curr = copy->next;  
    }  
  
    // 第二步：设置复制节点的random指针  
    curr = head;  
    while (curr) {  
        if (curr->random) {  
            curr->next->random = curr->random->next;  
        }  
        curr = curr->next->next;  
    }  
  
    // 第三步：将复制节点从原节点中分离出来  
    Node dummy; // 使用dummy头节点简化操作  
    Node* tail = &dummy;  
    curr = head;  
    while (curr) {  
        Node* copy = curr->next;  
        tail->next = copy;  
        tail = copy;  
        curr->next = copy->next;  
        curr = curr->next;  
    }  
  
    return dummy.next; // 返回新链表的头节点  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

在C语言中实现这个深拷贝链表的问题需要一些额外的步骤，因为C语言没有像Python或Java那样的内置哈希表来存储原始节点和它们对应的复制节点的映射关系。

1. 步骤一：遍历原链表，并在每个原节点后面插入一个复制节点。这样，原链表和复制节点就形成了交替的节点对。这一步确保了复制节点和原节点之间的直接对应关系，为后续的random指针设置提供了便利。
2. 步骤二：遍历新的链表（交替的节点对），为每个复制节点的random指针赋值。因为原节点和复制节点是交替的，所以可以直接通过原节点的random指针找到对应的复制节点，并设置复制节点的random指针。
3. 步骤三：再次遍历链表，将复制节点从原节点中分离出来，形成独立的复制链表。这一步通过将复制节点逐个链接到新的链表上，并断开与原链表的连接，完成了深拷贝的最后一步。

关于链表的其他题目
leetcode 链接
牛客 链接

五. 双向链表的基础操作*

带头+双向+循环链表增删查改实现

//带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
 LTDataType _data;
 struct ListNode* next;
 struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

下面给出具体代码实现，肖恩就不给大家一一分析了，和单链表的差不多

typedef int LTDataType;  
  
typedef struct ListNode {  
    LTDataType _data;  
    struct ListNode* next;  
    struct ListNode* prev;  
} ListNode;  
  
// 创建返回链表的头结点  
ListNode* ListCreate() {  
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));  
    if (!head) exit(EXIT_FAILURE);  
    head->next = head;  
    head->prev = head;  
    return head;  
}  
  
// 双向链表销毁  
void ListDestory(ListNode* plist) {  
    ListNode* cur = plist->next;  
    while (cur != plist) {  
        ListNode* temp = cur;  
        cur = cur->next;  
        free(temp);  
    }  
    free(plist);  
}  
  
// 双向链表打印  
void ListPrint(ListNode* plist) {  
    ListNode* cur = plist->next;  
    while (cur != plist) {  
        printf("%d ", cur->_data);  
        cur = cur->next;  
    }  
    printf("\n");  
}  
  
// 双向链表尾插  
void ListPushBack(ListNode* plist, LTDataType x) {  
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));  
    if (!newNode) exit(EXIT_FAILURE);  
    newNode->_data = x;  
    ListNode* tail = plist->prev;  
    tail->next = newNode;  
    newNode->prev = tail;  
    newNode->next = plist;  
    plist->prev = newNode;  
}  
  
// 双向链表尾删  
void ListPopBack(ListNode* plist) {  
    if (plist->next == plist) return; // 空链表  
    ListNode* tail = plist->prev;  
    ListNode* prev = tail->prev;  
    prev->next = plist;  
    plist->prev = prev;  
    free(tail);  
}  
  
// 双向链表头插  
void ListPushFront(ListNode* plist, LTDataType x) {  
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));  
    if (!newNode) exit(EXIT_FAILURE);  
    newNode->_data = x;  
    ListNode* head = plist;  
    head->next = newNode;  
    newNode->prev = head;  
    newNode->next = head->next;  
    head->next->prev = newNode;  
}  
  
// 双向链表头删  
void ListPopFront(ListNode* plist) {  
    if (plist->next == plist) return; // 空链表  
    ListNode* first = plist->next;  
    ListNode* next = first->next;  
    plist->next = next;  
    next->prev = plist;  
    free(first);  
}  
  
// 双向链表查找  
ListNode* ListFind(ListNode* plist, LTDataType x) {  
    ListNode* cur = plist->next;  
    while (cur != plist) {  
        if (cur->_data == x) {  
            return cur;  
        }  
        cur = cur->next;  
    }  
    return NULL;  
}  
  
// 双向链表在pos的前面进行插入  
void ListInsert(ListNode* pos, LTDataType x) {  
    if (!pos) return;  
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));  
    if (!newNode) exit(EXIT_FAILURE);  
    newNode->_data = x;  
    ListNode* prev = pos->prev;  
    prev->next = newNode;  
    newNode->prev = prev;  
    newNode->next = pos;  
    pos->prev = newNode;  
}  
  
// 双向链表删除pos位置的结点  
void ListErase(ListNode* pos) {  
    if (!pos || pos->next == pos) return; // 空链表或pos无效  
    ListNode* prev = pos->prev;  
    ListNode* next = pos->next;  
    prev->next = next;  
    next->prev = prev;  
    free(pos);  
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

那么看到这里呢，本篇文章也就接近尾声咯~~~
感谢大家的支持哦
为了表示我的歉意，这一篇给大家放两张照片！！！

下期预告~~~
环形链表详解
我们明天晚上见咯，应该是今天晚上（过12点了哈哈哈）