链表

链表的核心概念

链表是一种线性数据结构，其内部的物理存储单元非连续，非顺序，而是通过节点中的指针将所有元素串联而成

单链表的每个节点通常包含两部分：存储数据的变量和指向下一个节点的指针

节点结构体定义

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){}
};

链表的基本操作（创建、遍历、摧毁）

// 遍历并打印链表
void printList(ListNode* head){
    ListNode* cur=head;
    while(cur!=nullptr){
        cout<<cur->val<<"->";
        cur=cur->next;
    }
    cout<<"nullptr"<<endl;
}

// 摧毁链表，释放内存
void freeList(ListNode* head){
    ListNode* cur=head;
    while(cur!=nullptr){
        ListNode* temp=cur;
        cur=cur->next;
        delete temp; // 释放内存，防止内存泄漏
    }
}

int main(){
    // 创建一个包含节点1->2->3的单链表
    ListNode* head=new ListNode(1);
    head->next=new ListNode(2);
    head->next->next=new ListNode(3);
    
    printList(head);
    freeList(head);
    return 0;
}

---

链表的题解分析

处理链表问题的常用技巧：虚拟头结点、双指针和节点指针的断开与重写

翻转链表

题目描述：

翻转一个单链表，例如输入1->2->3->nullptr，输出3->2->1->nullptr

算法思路：

引入三个指针：pre(指向当前节点的前驱)、cur(指向当前节点)、temp(暂存当前节点的后继，防止断开连接后丢失)。在遍历过程中，将cur->next指向pre，然后整体向后移动。

class Solution{
    public:
        ListNode* reverseList(ListNode* head){
            ListNode* pre=nullptr;
            ListNode* cur=head;
            
            while(cur!=nullptr){
                ListNode* temp=cur->next; // 暂存后继节点
                cur->next=pre;                // 修改指针指向
                pre=cur;                      // pre暂存cur
                cur=temp;                 // cur访问下一节点
            }
            return pre; 
        }
}

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

题目描述：

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

算法思路

1. 虚拟头结点：在原链表头节点前添加一个辅助节点，用于统一处理删除头结点的边界情况

2. 快慢双指针：

   • 让fast指针先向前移动n+1步
   • 随后，fast和slow指针同步向前移动，直到fast到达nullptr
   • 此时，slow指针恰好指向待删除节点的前驱节点，执行slow->next=slow->next->next即可

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head); // 创建虚拟头节点
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        // 快指针先走 n + 1 步
        for (int i = 0; i <= n; ++i) {
            fast = fast->next;
        }

        // 快慢指针同步前移
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // 删除目标节点
        ListNode* target = slow->next;
        slow->next = slow->next->next;
        delete target; // 释放内存

        ListNode* retNode = dummy->next;
        delete dummy; // 释放虚拟头节点内存
        return retNode;
    }
};

---