List

06 Jul 2025

链表

1.如何构造一个链表？

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null。链表的入口节点称为链表的头结点也就是head。

struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
int main(){
    ListNode *head = new ListNode(1);  // 创建头节点
    ListNode *second = new ListNode(2);  // 创建第二个节点
    ListNode *third = new ListNode(3);  // 创建第三个节点
    head->next = second;  // 将头节点的next指向第二个节点
    second->next = third;  // 将第二个节点的next指向第三个节点
    third->next = NULL;  // 将第三个节点的next指向NULL
    cout<<head->val<<" -> "<<head->next->val<<" -> "<<head->next->next->val<<endl;  // 输出链表的值
    // 释放内存
    delete head;
    delete second;
    delete third;
    return 0;  // 程序结束
}

1. 链表节点结构体 (ListNode):
   • int val: 存储节点的值。
   • ListNode *next: 指向下一个节点的指针。
   • 构造函数 ListNode(int x): 初始化节点值和将next指针设为NULL。
2. main函数中的链表创建:
   • 创建头节点 head，值为1。
   • 创建第二个节点 second，值为2。
   • 创建第三个节点 third，值为3。
   • 通过next指针连接这些节点：
     • head->next = second。
     • second->next = third。
     • third->next = NULL (表示链表结束)。

链表有很多种，上图的单链表是一种，还有双链表，循环链表，循环双链表，如STL库里的list就是循环双链表。

2.删除链表中元素

删除链表中等于给定值 val 的所有节点。以链表1->4->2->4 来举例，移除元素4。

删除4这个元素，只需要判断current->next->val是否等于4，如果相等，current->next=current->next->next，然后在内存中删掉4这个节点，如果不是，那就current=curenr->next，移动到下一个位置，最后返回head。

如果是删除1这个元素，1是头节点，这里的逻辑就和删除中间节点不一样。

如图，应该是将head移动到head->next这个位置，然后在内存中删掉第一个节点。

如果我们需要统一一个逻辑在做这道题，需要一个虚拟的头节点。

这样不管是删掉第一个还是其他的元素，都是用的一个逻辑。

#include<iostream>
using namespace std;
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
//直接对链表进行操作
ListNode* removeElements(ListNode* head,int val){
    while(head !=NULL && head->val==val){
        ListNode* temp=head;//保留头节点
        head=head->next;//将头节点指向下一个节点
        delete temp;//释放头节点的内存
    }
    ListNode* current=head;//当前节点指针
    while(current !=NULL && current->next !=NULL){
        if(current->next->val==val){
            ListNode* temp=current->next; // 保留要删除的节点
            current->next=current->next->next; // 删除当前节点的下一个节点
            delete temp; // 释放内存
        }else{
            current=current->next;
        }
    }
    return head; // 返回新的头节点
}

//利用虚拟头节点删除
ListNode* removeElementsWithDummy(ListNode* head,int val){
    ListNode* dummy=new ListNode(0);//这是一个虚拟的头节点
    dummy->next=head;
    ListNode* current=dummy;
    while(current !=NULL && current->next !=NULL){
        if(current->next->val==val){
            ListNode* temp=current->next; // 保留要删除的节点
            current->next=current->next->next; // 删除当前节点的下一个节点
            delete temp; // 释放内存
        }else{
            current=current->next;
        }
    }
    //如果直接这样返回的话，虚拟的没有得到释放，会造成内存管理的混乱
    //return dummy->next;
    head = dummy->next;
    delete dummy;
    return head;
}

int main(){
    // 创建链表
    ListNode *head = new ListNode(1);
    ListNode *second = new ListNode(2);
    ListNode *third = new ListNode(6);
    ListNode *fourth = new ListNode(3);
    ListNode *fifth = new ListNode(4);
    ListNode *sixth = new ListNode(5);
    ListNode *seventh = new ListNode(6);
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    fifth->next = sixth;
    sixth->next = seventh;
    seventh->next = NULL;

    // 删除值为6的节点
    //head = removeElements(head, 1);
    head = removeElementsWithDummy(head, 6);
    // 输出链表
    ListNode* current = head;
    while(current != NULL){
        cout << current->val << " ";
        current = current->next;
    }
    
    // 释放内存
    current = head;
    while(current != NULL){
        ListNode* temp = current;
        current = current->next;
        delete temp;
    }
    
    return 0; // 程序结束
}

3.设计链表

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

第四点的逻辑如下图所示：

先将一个东西移动到index-1处，然后current->next=addelem，addelem>next = current->next。

最后一个删除指定位置的index。

#include<iostream>
using namespace std;
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
class MyLinkedList {
private:
    ListNode* head;  // 链表的头节点
    int size;  // 链表的大小
public:
    MyLinkedList() {
        head =new ListNode(0);  // 初始化头节点为虚拟节点
        size = 0;  // 初始化链表大小为0
    }
    int get(int index) {
        if(index<0||index>=size){
            return -1;
        }
        ListNode* current=head->next;
        for(int i=0;i<index;i++){
            current=current->next;  // 遍历到指定索引的节点
        }
        return current->val;  // 返回节点的值
    }
    
    void addAtHead(int val) {
        addAtIndex(0, val);  // 在头部添加节点
    }
    
    void addAtTail(int val) {
        addAtIndex(size, val);  // 在尾部添加节点
    }
    
    void addAtIndex(int index, int val) {
        if(index > size) {
            cout << "Index out of bounds, node not added." << endl;
            return;  // 如果索引超出范围，返回
        }
        if(index < 0) {
            index = 0;  // 如果index小于0，则在头部插入节点
        }
        
        ListNode* current = head;
        for(int i = 0; i < index; i++) {
            current = current->next;  // 遍历到指定索引的前一个节点
        }
        ListNode* newNode = new ListNode(val);  // 创建新节点
        newNode->next = current->next;
        current->next = newNode;
        size++;  // 增加链表大小
    }
    
    void deleteAtIndex(int index) {
        if(index < 0 || index >= size) {
            cout << "Index out of bounds, node not deleted." << endl;
            return;
        }
        
        ListNode* current = head;
        for(int i = 0; i < index; i++) {
            current = current->next;  // 遍历到指定索引的前一个节点
        }
        ListNode* p = current->next;
        current->next = current->next->next;
        delete p;
        size--;  // 减少链表大小
    }
};
int main(){
    // 测试代码
    MyLinkedList* obj = new MyLinkedList();
    obj->addAtHead(1);
    obj->addAtTail(3);
    obj->addAtIndex(1, 2);
    cout << obj->get(1) << endl;  // 应该输出2
    obj->deleteAtIndex(1);
    cout << obj->get(1) << endl;  // 应该输出3
    delete obj;
    return 0;
}

4.反转链表

反转一个单链表。输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL。

首先要把 cur->next 节点用tmp指针保存一下，也就是保存这个节点。保存一下这个节点是因为接下来要改变 cur->next 的指向，将cur->next 指向pre ，此时已经反转了第一个节点。接下来，就是循环走如下代码逻辑，继续移动pre和cur指针。最后，cur指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以，pre指针就指向了新的头结点。

#include<iostream>
using namespace std;
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
// 反转链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev=NULL;  // 前一个节点初始化为NULL
    ListNode* current=head;  // 当前节点指向头节点
    while(current){
        ListNode* temp=current->next;  // 保存当前节点的下一个节点
        current->next=prev;  // 将当前节点的next指向前一个节点
        prev=current;  // 前一个节点更新为当前节点
        current=temp;  // 当前节点更新为下一个节点
    }
    return prev;  // 返回新的头节点，即原链表的尾节点
}
int main(){
    ListNode *head = new ListNode(1);
    ListNode *second = new ListNode(2);
    ListNode *third = new ListNode(3);
    ListNode *fourth = new ListNode(4);
    ListNode *fifth = new ListNode(5);
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    cout << "Original List: ";
    ListNode* current = head;
    while(current) {
        cout << current->val << " ";
        current = current->next;
    }
    cout << endl;
    ListNode* reversedHead = reverseList(head);  // 调用反转函数
    cout << "Reversed List: ";
    current = reversedHead;
    while(current) {
        cout << current->val << " ";  // 输出反转后的链表
        current = current->next;
    }
    return 0;  // 程序结束
}

这道题还有一个递归的解法。

ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }

递归基例

if (!head || !head->next) {
    return head;
}

• 如果链表为空（!head）或只有一个节点（!head->next），直接返回当前头节点，因为无需反转。

递归步骤

ListNode* newHead = reverseList(head->next);

• 递归调用，反转以head->next开头的子链表，并返回新头节点newHead。
• 假设递归调用正确反转了子链表，此时head->next已经是子链表的尾节点。

反转当前节点

head->next->next = head;
head->next = nullptr;

1. head->next->next = head：将当前节点head接在已反转子链表的尾部。
2. head->next = nullptr：断开当前节点与原下一个节点的连接，避免循环。

返回新头节点

return newHead;

• 在整个递归过程中，newHead始终是最初链表的尾节点，即反转后的新头节点，因此直接返回。

5.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

保存两个临时节点temp1=current->next，temp2=current->next->next->next。 然后分别执行步骤一current->next=current->next->next，步骤二current->next->next=temp，步骤三current->next->next->next=temp2。

#include<iostream>
using namespace std;
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
ListNode* change(ListNode* head){
    ListNode* dummy=new ListNode(0);  // 创建一个虚拟头节点
    dummy->next = head;  // 将虚拟头节点的next指向原链表的头节点
    ListNode* current = dummy;  // 当前节点指针初始化为虚拟头节点
    while(current->next !=nullptr&&current->next->next !=nullptr){
        ListNode* temp=current->next;
        ListNode* temp1=current->next->next->next;
        current->next = current->next->next;    // 步骤一
        current->next->next = temp;          // 步骤二
        current->next->next->next = temp1;   // 步骤三

        current = current->next->next; // cur移动两位，准备下一轮交换
    }
    ListNode* result = dummy->next;
    delete dummy;
    return result;
}
int main(){
    ListNode *head = new ListNode(1);
    ListNode *second = new ListNode(2);
    ListNode *third = new ListNode(3);
    ListNode *fourth = new ListNode(4);
    ListNode *fifth = new ListNode(5);
    head->next = second;
    second->next = third;
    third->next = fourth;
    fourth->next = fifth;
    ListNode* changehead=change(head);  // 调用change函数
    ListNode* current = changehead;
    while(current) {
        cout << current->val << " ";  // 输出链表的值
        current = current->next;  // 移动到下一个节点
    }
    cout << endl;  // 输出换行
    return 0;  // 程序结束
}

6.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。进阶：你能尝试使用一趟扫描实现吗？

这是双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

定义fast指针和slow指针，初始值为虚拟头结点。 fast首先走n + 1步 ，只有这样同时移动的时候slow才能指向删除节点的上一个节点。 fast和slow同时移动，直到fast指向末尾。 删除slow指向的下一个节点 。

#include<iostream>
using namespace std;
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
ListNode* deleteN(ListNode* head,int n){
    ListNode* dummp=new ListNode(0);  // 创建一个虚拟头节点
    dummp->next=head;
    ListNode* fast=dummp;  // 快指针
    ListNode* slow=dummp;  // 慢指针
    for(int i=0;i<n;i++){
        fast=fast->next;  // 快指针先走n步
    }
    while(fast->next!=NULL){
        fast=fast->next;
        slow=slow->next;
    }
    slow->next=slow->next->next;
    return dummp->next;  // 返回新的头节点
}
int main(){
    ListNode* head=new ListNode(1);
    head->next=new ListNode(2);
    head->next->next=new ListNode(3);
    head->next->next->next=new ListNode(4);
    head->next->next->next->next=new ListNode(5);
    int n=2;  // 删除倒数第n个节点
    ListNode* newHead=deleteN(head,n);
    ListNode* current=newHead;
    while(current!=NULL){
        cout << current->val << " ";  // 输出新的链表
        current=current->next;
    }
    cout << endl;
    // 释放链表内存
    current = newHead;
    while (current != NULL) {
        ListNode* temp = current;
        current = current->next;
        delete temp;  // 删除当前节点
    }
    return 0;  // 程序结束
}

7.链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。

显而易见的只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB。

既然是相交节点，相交节点的后续部分一定完全一致，毕竟相交节点对于两个列表来说就是同一个节点，那么也就是说相交节点以及后续部分一定是位于列表最后部分的。所以只需要计算长列表和短列表的差值，即末端对齐，把长列表的pA移动到和pB一样的起点，之后同步向后移，只要有相交节点那么必然能同时相遇，返回即可，如果都是null那就返回null。

上下两个是不同的例子。

#include<iostream>
using namespace std;
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};
ListNode* meet(ListNode* head1, ListNode* head2){
    if(head1 == NULL || head2 == NULL) return NULL;  // 如果任一链表为空，返回NULL
    ListNode* p1=head1;
    int size1;  // 指向链表1的指针
    ListNode* p2=head2;
    int size2;  // 指向链表2的指针
    while(p1 != NULL){  // 计算链表1的长度
        size1++;
        p1 = p1->next;
    }
    while(p2 != NULL){  // 计算链表2的长度
        size2++;
        p2 = p2->next;
    }
    p1=head1;  // 重置p1指向链表1的头节点
    p2=head2;  // 重置p2指向链表2的头节点
    if(size1 > size2){  // 如果链表1更长
        for(int i=0; i<size1-size2; i++){  // 让p1先走size1-size2步
            p1 = p1->next;
        }
    }else{  // 如果链表2更长或两者相等
        for(int i=0; i<size2-size1; i++){  // 让p2先走size2-size1步
            p2 = p2->next;
        }
    }
    while(p1 != NULL && p2 != NULL){  // 同时遍历两个链表
        if(p1 == p2) return p1;  // 如果相遇，返回相遇的节点
        p1 = p1->next;  // p1向后移动
        p2 = p2->next;  // p2向后移动
    }
    return NULL;  // 如果没有相遇，返回NULL
}
int main(){
    ListNode* head1 = new ListNode(1);
    head1->next = new ListNode(2);
    head1->next->next = new ListNode(3);
    ListNode* head2 = new ListNode(4);
    head2->next = new ListNode(5);
    head2->next->next = head1->next;  // 让head2与head1相交
    ListNode* meetNode = meet(head1, head2);  // 查找相遇节点
    if(meetNode != NULL){
        cout << "Meet at node with value: " << meetNode->val << endl;  // 输出相遇节点的值
    }else{
        cout << "No meeting point." << endl;  // 如果没有相遇，输出提示信息
    }
    // 释放链表内存
    delete head1->next->next;  // 删除链表1的第三个节点
    delete head1->next;  // 删除链表1的第二个节点
    delete head1;  // 删除链表1的头节点
    delete head2->next;  // 删除链表2的第二个节点
    delete head2;  // 删除链表2的头节点
    return 0;  // 程序结束
}

8.环形链表

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。

判断是否有环可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。首先，fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇 ，为什么fast指针和slow指针一定会相遇呢？可以画一个环，可以认为是fast指针在任意一个节点开始追赶slow指针。fast指针速度更快，所以必然相遇。

接下来要找这个环的入口，假设从头结点到环形入口节点的节点数为x（4）。 环形入口节点到 fast指针与slow指针相遇节点节点数为y（1）。 从相遇节点再到环形入口节点节点数为 z（3）。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， z + y为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2： \((x + y) * 2 = x + y + n (y + z)\) 两边消掉一个 （x+y）:x + y = n (y + z)。

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从 n (y + z)中提出一个 y + z来，整理公式之后为如下公式：x = (n - 1) (y + z) + z ，这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明：

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 检测是否有环，并返回相遇点
ListNode* detectCycle(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return nullptr;
    
    ListNode* slow = head;
    ListNode* fast = head;
    
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return slow; // 相遇点
        }
    }
    
    return nullptr; // 无环
}

// 找到环的起始节点
ListNode* findCircleStart(ListNode* head) {
    ListNode* meet = detectCycle(head);
    if (meet == nullptr) return nullptr; // 无环
    
    ListNode* slow = head;
    while (slow != meet) {
        slow = slow->next;
        meet = meet->next;
    }
    
    return slow; // 环的起始节点
}

ListNode* createCircleList(int n) {
    if (n <= 0) return nullptr;
    ListNode* head = new ListNode(1);
    ListNode* current = head;
    for (int i = 2; i <= n; ++i) {
        current->next = new ListNode(i);
        current = current->next;
    }
    current->next = head; // 形成环
    return head;
}

int main() {
    int n = 5;
    ListNode* head = createCircleList(n);
    ListNode* circleStart = findCircleStart(head);
    
    if (circleStart != nullptr) {
        cout << "Circle starts at node with value: " << circleStart->val << endl;
    } else {
        cout << "No circle found." << endl;
    }
    
    // 释放内存（需要先断开环）
    if (n > 0) {
        ListNode* current = head;
        for (int i = 0; i < n; ++i) {
            ListNode* temp = current;
            current = current->next;
            delete temp;
        }
    }
    
    return 0;
}