当前位置： 首页 > article >正文

链表知识汇总

article 2024/11/14 14:44:05

链表知识汇总

1.基础知识

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

1.1链表的类型

**单链表：**每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），单链表中的指针域只能指向节点的下一个节点。

**双链表：**每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。既可以向前查询也可以向后查询。

循环链表：是链表首尾相连。

1.2链表的存储方式

数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。链表是通过指针域的指针链接在内存中各个节点。

所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

1.3 链表的定义

//单链表定义
struct ListNode {
    int val;  // 节点上存储的元素
    ListNode *next;  // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {}  // 节点的构造函数
};

//双链表定义
private:
	template <typename E>
	class ListNode{
    public:
        E val;
        ListNode* next;
        ListNode* prev;
        
       ListNode(ListNode* prev, E element, ListNode* next){
            this->val=element;
            this->next=next;
            this->prev=prev;
        }
    };

注意：

  1. 编程语言标准库一般都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。
  2. 编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 next 指针，指向下一个节点；而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。

1.4虚拟头结点的创建

使用虚拟头结点的优点

  1. 简化插入和删除操作：有了虚拟头结点，无论是插入还是删除操作都无需特殊处理链表头节点。
  2. 统一操作逻辑：避免处理头节点和其他节点时的代码差异，使代码逻辑更加一致。
  3. 防止空指针异常：当链表为空或只包含一个节点时，虚拟头结点能减少空指针检查。

可以将虚拟头结点定义为一个指针并动态分配内存，或者直接在栈上创建。以下是创建虚拟头结点的几种方法：

1. 使用动态分配的虚拟头结点

动态分配一个空节点，通常将其 data 设为 0 或不进行初始化（取决于需求）。next 指针指向实际的链表头节点。

Node* dummyHead = new Node(0);// 创建一个虚拟头结点，data 为 0
dummyHead->next = nullptr;  // 初始时链表为空，虚拟头结点的 next 也指向 nullptr

在这种情况下，dummyHead 本身不保存实际数据，仅作为占位节点。

2. 使用栈上分配的虚拟头结点

可以在栈上创建虚拟头结点，避免动态分配的内存管理。这样虚拟头结点的生命周期会随作用域结束自动释放。

Node dummyHead(0);    // 栈上分配的虚拟头结点
dummyHead.next = nullptr;
Node* head = &dummyHead;  // head 指向虚拟头结点
特点动态分配虚拟头结点栈上分配虚拟头结点
生命周期管理手动控制，适合长期存在受作用域限制，离开作用域后自动释放
内存管理必须手动释放，防止内存泄漏自动管理，无需手动释放
编程复杂性代码稍复杂，需手动管理内存简洁省事，适合短期链表
性能堆分配较慢，适合大链表栈分配速度快，适合小规模链表
适用场景跨函数或长期链表函数内的短期链表

总结：

  • 动态分配适合长期使用、需要传递的链表，但需手动管理内存。
  • 栈上分配适合局部、短期链表操作，自动管理内存、代码更简洁。

1.5 p1.next和p1->next有什么区别

p1.next 和 p1->next 的区别在于 p1 的类型不同：

  • .用于对象，直接访问对象的成员。
  • -> 用于指针，通过指针访问所指向对象的成员。

  1. p1.next：

    • 使用点号（.）访问成员变量，表示 p1 是一个对象。
    • 例如，如果 p1 是 ListNode 类型的对象，那么 p1.next 可以访问 p1 的成员变量 next。
    ListNode p1(0);    // `p1` 是一个对象
p1.next = nullptr; // 使用 `p1.next` 访问成员变量

  2. p1->next：

    • 使用箭头（->）访问成员变量，表示 p1 是一个指针。
    • 如果 p1 是一个指向 ListNode 类型的指针，那么 p1->next 可以访问它所指向对象的成员变量 next。
    ListNode* p1 = new ListNode(0); // `p1` 是一个指针
p1->next = nullptr;             // 使用 `p1->next` 访问成员变量

2.基础链表练习题

203. 移除链表元素(虚拟头结点)

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

解题代码：

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
    //头结点有时候也要删除，那么就在头结点的前面加个虚拟头结点方便删除头结点
    ListNode* dumhead = new ListNode(0);
    dumhead->next = head;
    ListNode* cur = dumhead;//这个是移动指针
    while(cur->next!=NULL){
        if(cur->next->val==val){
            ListNode* tmp=cur->next;//保存需要删除节点的地址，方便后面进行删除
            cur->next=cur->next->next;
            delete tmp;
        }else{
            cur=cur->next;
        }
    }
    head=dumhead->next;//返回修改后的链表头地址
    delete dumhead;
    return head;
    }
};

完整ACM模式代码，含链表创建，链表输出打印内容：

#include<iostream>
#include <limits>
using namespace std;

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

ListNode* creatNodeList(){
    ListNode* head=NULL;
    ListNode* tail=NULL;  
    int num;
    while(cin>>num){
        ListNode* newnode = new ListNode(num);
        if(head==NULL){
            head=newnode;
            tail=newnode;
        }else{
            tail->next=newnode;
            tail=newnode;
        }
    }
    // 清除 cin 的错误状态以便后续继续输入
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
    tail->next = NULL;
    return head;
}

void printNodeList(ListNode* head){
    ListNode* current = head;
    while(current!=NULL){
        if(current->next!=NULL){
            cout<<current->val<<" -> ";
        }else{
             cout<<current->val<<endl;
        }
        current=current->next;
    }
    cout<<endl;
}

ListNode* removeElements(ListNode* head, int val){
    //头结点有时候也要删除，那么就在头结点的前面加个虚拟头结点方便删除头结点
    ListNode* dumhead = new ListNode(0);
    dumhead->next = head;
    ListNode* cur = dumhead;//这个是移动指针
    while(cur->next!=NULL){
        if(cur->next->val==val){
            ListNode* tmp=cur->next;//保存需要删除节点的地址，方便后面进行删除
            cur->next=cur->next->next;
            delete tmp;
        }else{
            cur=cur->next;
        }
    }
    //返回修改后的链表头地址,如果没有这个操作，直接返回head，返回的可能是一个被删除的节点
    head=dumhead->next;
    delete dumhead;
    return head;
}

int main(){
    cout<<"请按照头尾节点顺序依次输入节点值:"<<endl;
    ListNode* myNode=creatNodeList();

    cout<<"你输入的链表如下所示:"<<endl;
    printNodeList(myNode);

    int val; 
    cout<<"请输入一个需要删除的节点"<<endl;
    while(cin>>val){
        myNode=removeElements(myNode,val);
        cout<<"修改后的链表如下所示:"<<endl;
        printNodeList(myNode);
    }
    return 0;
}

21. 合并两个有序链表（虚拟头结点）

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        //在栈上创建虚拟头结点，仅限于函数内使用，不能跨函数使用
        ListNode dummyHead(0); dummyHead.next=nullptr;
        //创建一个指针指向虚拟头结点，方便后面合并链表
        ListNode* p = &dummyHead;
        //创建两个指针分别指向list1和list2
        ListNode* p1=list1; ListNode* p2=list2;

        while(p1!=nullptr&&p2!=nullptr){
            //比较list1(p1)和list2(p2)哪个值小
            if(p1->val > p2->val){
                p->next=p2;//list2(p2)小，就将p2现在这个节点加入到dummyHead(p)链表中
                p2=p2->next;//list2(p2)对应节点加入后，前进一位
            }else{
                p->next=p1;//list1(p1)小，就将p1现在这个节点加入到dummyHead(p)链表中
                p1=p1->next;//list1(p1)对应节点加入后，前进一位
            }
            p=p->next;//dummyHead(p)前移一位
        }
        //如果list1(p1)没有了，就把剩下的list2(p2)接在dummyHead(p)后面
        if(p1==nullptr){
            p->next=p2;
        }
        //如果list2(p2)没有了，就把剩下的list1(p1)接在dummyHead(p)后面
        if(p2==nullptr){
            p->next=p1;
        }
        //返回dummyHead(p)的next指针，就是新合并链表的第一个节点地址
        return dummyHead.next;
    }
};

86. 分隔链表(2个链表然后合并)

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode dummyNode1(0);//比ListNode dummyNode = ListNode(0);效率高
        ListNode dummyNode2(0);
        ListNode* p1 = &dummyNode1;
        ListNode* p2 = &dummyNode2;
        ListNode* p = head;
        while(p!=nullptr){
            if(p->val<x){
                p1->next = p;
                p1=p1->next;
            }else{
                p2->next = p;
                p2=p2->next;
            }
            p=p->next;
        }
        //在链表的分割操作中，应该确保 p2 结束的节点的 next 指针指向 nullptr，以避免形成环路
        p2->next=nullptr;//这一步忘记了，程序出现bug了
        p1->next=dummyNode2.next;
        return dummyNode1.next;
    }
};

23. 合并 K 个升序链表(最小堆)

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        //因为涉及到同时对k个元素大小进行比较，所以本地需要用最小堆自动实现大小排序
        ListNode dummyNode(0);
        ListNode* p = &dummyNode;
        //定义Lambda表达式作为小顶堆比较器
        auto min = [](ListNode* a , ListNode* b){
            return a->val > b ->val;//谁大谁的优先级就低
        };
        //构建优先级队列（小顶堆）
        priority_queue<ListNode*,vector<ListNode*>,decltype(min)> minH(min);
        //将lists里面每个链表的头节点放进去，因为每个链表是升序的
        for(ListNode* head : lists){
            if(head!=nullptr){
                minH.push(head);
            }
        }
        while(!minH.empty()){
            ListNode* node=minH.top();
            minH.pop();
            p->next = node;
            //头结点比较出最小的后，把这个头结点的后面节点也加入最小堆中
            if(node->next!=nullptr){
                minH.push(node->next);
            }
            p=p->next;
        }
        return dummyNode.next;
    }
};

19. 删除链表的倒数第 N 个结点(快指针先走k后，慢指针走)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummyHead(0);
        dummyHead.next=head;//这个忘写了，也整错了
        ListNode* p1 = &dummyHead;
        ListNode* p2 = &dummyHead;
        while(n-- && p1!=nullptr){
            p1=p1->next;
        }
        p1=p1->next;//这个得多一步，后面方便删除节点

        while(p1!=nullptr){//开始写成if了，整错了
            p1=p1->next;
            p2=p2->next;
        }
    
        ListNode* temp = p2->next;
        p2->next=p2->next->next;
        delete temp;
       
        return dummyHead.next;
    }
};

876. 链表的中间结点(快慢指针差2倍)

给你单链表的头结点 head ，请你找出并返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow=head;//慢指针每次走一步，用于返回中间节点
        ListNode* fast=head;//快指针每次走两步，用于遍历整个链表
        while(fast != nullptr && fast->next != nullptr){//模拟一下来设置边界条件
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
};

（这道题是我第一次实习面试时候，面试官直接让我写完整实现程序，也就是ACM模式，当时一点也不熟悉，甚至在本地编辑器都不会写ListNode的创建，愣是反应半天没写出来，现在我把完整代码附在下面）

#include<iostream>
#include <limits>
using namespace std;

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

ListNode* creatListNode(){
    ListNode* head=nullptr;
    ListNode* tail=nullptr;
    int num;
    while(cin>>num){
        ListNode* newnode = new ListNode(num);
        if(head==nullptr){
            head=newnode;//如果头结点是空指针说明还没有节点
            tail=newnode;//头尾指针都指向第一个节点
        }else{
            tail->next=newnode;//尾指针指在最后一个节点，那么这个节点的下个节点插入newnode
            tail=newnode;//尾指针继续指向最后的节点
        }
    }
    // 清除 cin 的错误状态以便后续继续输入
    cin.clear();
    cin.ignore(numeric_limits<streamsize>::max(), '\n'); 
    tail->next = NULL;
    return head;
}

void printNode(ListNode* head){
    ListNode* p = head;
    while(p!=nullptr){
        if(p->next!=nullptr){
            cout<<p->val<<" -> ";
        }else{
            cout<<p->val;
        }
        p=p->next;
    }
    cout<<endl;
}

ListNode* midFindNode(ListNode* inNode){
    ListNode* fast=inNode;
    ListNode* slow=inNode;
    while(fast!=nullptr&&fast->next!=nullptr){
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

int main(){
    cout<<"请按照头尾节点顺序依次输入节点值:"<<endl;
    ListNode* inNode = creatListNode();
    ListNode* midnode = midFindNode(inNode);
    cout<<"从中间节点依次往后的节点为："<<endl;
    printNode(midnode);
}

142. 环形链表 II(快慢指针差两倍)

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

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

/*和寻找中间节点一样，fast走2步，slow走一步，然后累计差是1,2,3…n，
  若fast=null，没有环，已到头；若fast=slow，说明相遇，肯定有环。
  相遇点距离头结点距离就是走的k次，且圆环节点数为k的整数倍(两指针差的距离k)
  求圆环起点，则让其中一个指针回到都节点，都一次一步，最终相遇点就是圆环起点(图说明更形象)*/
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow=head;
        ListNode *fast=head;
        while(fast!=NULL&&fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                break;//说明相遇，赶紧退出，保留指针位置
            }
        }
        if(fast==NULL||fast->next==NULL){
            return NULL;//有null，没相遇，直接返回null
        }
        slow=head;//回退到头指针
        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return slow;
    }
};//快慢指针

160. 相交链表(计算长度差后先后走)

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

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

 /*这道题准备先分别计算各自长度，然后长的先走相差的步数后，慢的再走*/
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * p1 = headA;
        ListNode * p2 = headB;
        int len1=0, len2=0;
        while(p1!=NULL){
            len1++;
            p1=p1->next;
        }
        while(p2!=NULL){
            len2++;
            p2=p2->next;
        }
        ListNode * a1 = headA;
        ListNode * a2 = headB;
        if(len1>len2){
            int len=len1-len2;
            while(len--){
                a1=a1->next;
            }
        }
        if(len2>len1){
            int len=len2-len1;
            while(len--){
                a2=a2->next;
            }
        }
        while(a1!=NULL){
            if(a1==a2){
                return a1;
            }
            a1=a1->next;
            a2=a2->next;
        }
        return NULL;
    }
};

206. 反转链表()

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p1=head;
        ListNode* p2=NULL; //可以将指针设为NULL
        while(p1!=nullptr){
            ListNode* temp;
            temp=p1->next;
            p1->next=p2;
            p2=p1;
            p1=temp;
        }
        return p2;//写成返回p1了，p1到时候已经是null了
    }
};

http://www.kler.cn/a/388113.html

相关文章：

  • 网络远程操控
  • unity基础，点乘叉乘。
  • RoseTTAFold MSA_emb类解读
  • Linux相关习题-gcc-gdb-冯诺依曼
  • 腾讯云nginx SSL证书配置
  • uniapp 设置安全区域
  • 手机的ip地址是固定的吗？多角度深入探讨
  • 【Linux】Linux入门实操——vim、目录结构、远程登录、重启注销
  • 第9章 Apache WEB服务器企业实战
  • ChatGPT 新体验：AI 搜索功能与订阅支付指南
  • 加固筑牢安全防线：多源威胁检测响应在企业网络安全运营中的核心作用
  • leetcode 832.翻转图像
  • Vue Router 详细使用步骤：如何在 Vue 项目中配置 Vue Router
  • 世优科技携手人民中科打造AI数字人智能体助力智慧校园
  • Vue vs React：两大前端框架的区别解析
  • Cannot read properties of undefined (reading ‘$isServer‘)
  • [强网杯 2019]随便注 1
  • 解决Mac M芯片 Wireshark 运行rvictl -s 后，出现Starting device failed
  • Java中的I/O模型——BIO、NIO、AIO
  • 华为大变革？仓颉编程语言会代替ArkTS吗？
  • 机器学习系列-----主成分分析（PCA）
  • Redis的内存淘汰机制
  • WPF在MVVM模式下怎么实现导航功能
  • 【SpringBoot】ThreadLocal线程空间上下文使用
  • Linux:版本控制器git的简单使用+gdb/cgdb调试器的使用
  • 【国内中间件厂商排名及四大中间件对比分析】