链表

概述

链表的概念

链表是一种在物理存储上非连续的线性数据结构，数据元素的逻辑顺序是通过指针来维护的。想象一下，如果数组是一排整齐的储物柜，那么链表就像是一串通过绳子连接的珠子，每个珠子（结点）可以散落在任意位置，但通过绳子（指针）始终保持着它们之间的联系。

链表的核心特征是，数据分散存储在动态生成的结点中，每个结点的先后顺序通过指针来维护。就像是一场寻宝游戏，每个宝箱（结点）里不仅存有宝物（数据），还有一张藏有下一个宝箱位置的藏宝图（指针）。

如下图所示是一个经典的单链表，它由多个结点组成，每个结点都存储在不同的物理地址上，前一个结点存储了后一个结点的物理地址，进而保证结点之间的先后顺序。 其中头指针就像是整个寻宝图的起点，它存储着第一个宝箱（头结点）的位置。通过这个起点，我们就能顺着线索找到整条链表上的所有结点。

核心结构

每个链表结点就像是一个小容器，由两个重要的部分组成：

• 数据域：这是容器的主要存储区，用于存放实际的数据内容。可以是任何类型的数据，比如：
  • 整数：比如学生的学号、年龄
  • 字符串：比如姓名、地址
  • 对象：比如一个完整的学生信息记录
• 指针域：这就像是容器上的标签或指示牌，记录着下一个容器（结点）在内存中的位置。通过这个"指示牌"，我们就能找到链表中的下一个结点。

这种结构设计使得链表非常灵活。想象一个火车，每个车厢就是一个结点：车厢里装着货物（数据域），车厢之间通过车钩相连（指针域）。我们可以随时添加或移除车厢，只需要调整相应的连接即可。

主要类型

根据结点指针域的不同，链表的类型也不同：

• 单向链表：每个结点只存储后继结点的内存地址。
• 双向链表：每个结点存储了前驱结点和后继结点的内存地址。
• 单向循环链表：在单向链表中，尾结点后继结点的地址存储的是空指针。单向循环链表在单向链表的基础上，将首结点看作尾结点的后继结点，即可形成单向循环链表。
• 双向循环链表：在双向链表中，首结点前驱结点的地址和尾结点后继结点的地址存储的都是空指针。双向循环链表在双向链表的基础上，将首结点看作尾结点的后继结点，尾结点看成首结点的前驱结点，即可形成双向循环链表。

核心特性

链表作为一种基础的数据结构，具有以下三个核心特性，这些特性决定了它在不同场景下的应用价值：

• 动态内存管理：

  • 特点：链表在存储上是非连续的，不需要预先分配固定大小的内存空间，结点可以按需动态生成。
  • 优势：特别适合无法预知最终数据量的场景，比如即时聊天的消息列表，可以随着新消息的到来动态增长。
  • 应用：在文件系统中，文件分配表就采用了链表结构，使得文件可以分散存储在磁盘的不同位置。

• 不支持随机访问：

  • 特点：由于链表在存储上是非连续的，访问任意位置的元素都需要从头结点开始遍历。
  • 限制：想要访问第n个元素，必须先访问前n-1个元素，时间复杂度为O(n)。
  • 应用场景：更适合那些主要以顺序访问为主的场景，比如音乐播放列表，我们通常是顺序播放或者只需要访问上一首/下一首。

• 高效的增删操作：

  • 特点：插入或删除结点只需要调整相邻结点的指针，时间复杂度为O(1)（不考虑查找过程）。
  • 优势：相比数组的插入删除操作（可能需要移动大量元素），链表的操作更加高效。
  • 实际应用：比如浏览器的前进/后退功能，就可以用双向链表来实现，每个网页就是一个结点，访问新页面就是插入操作，后退就是指针移动操作。

什么时候选择链表

链表和数组常常被用于比较，那么什么时候选择链表呢？ 链表的核心特点就是可以对动态的数据进行高效管理，当应用场景需要频繁增删数据、内存需要灵活分配或者实现复杂的数据结构的时候，链表是很好的选择；而数组适合数据稳定，需要支持随机访问的场景。两种数据结构互补，在实际应用中，需要根据需求权衡选择。

应用及代码示例

前面已经说过，链表根据指针域的不同，有多种表现形式。但是，最基础，最核心，同时也是面试算法题中最常见的链表形式就是单链表，所以下面主要围绕单链表进行讲解。

如何定义一个链表

由于链表是由多个结点组成的线性结构，所以定义链表也就是定义链表结点，一个链表的头结点也就代表了这个链表。

C++

以下C++代码在结构体中定义了一个单链表。可以看到，这个单链表的数据域是一个int类型的val,指针域是一个ListNode*类型的next,next存储的是后继结点的地址。同时，提供了三个构造函数用来初始化一个链表结点。

// 定义链表节点的结构体
struct ListNode {
    int val;        // 数据域：存储节点的值
    ListNode *next; // 指针域：指向下一个节点的指针
    
    // 构造函数1：默认构造，创建值为0的节点，指针指向nullptr
    ListNode() : val(0), next(nullptr) {}
    // 构造函数2：创建值为x的节点，指针指向nullptr
    ListNode(int x) : val(x), next(nullptr) {}
    // 构造函数3：创建值为x的节点，并指定下一个节点
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Java

以下Java代码在类中定义了一个单链表。可以看到，这个单链表的数据域是一个int类型的val,指针域是一个ListNode类型的next,next存储的是后继结点的（对象的引用）地址。同时，提供了三个构造函数用来初始化一个链表结点。

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Python

以下Python代码在类中定义了一个单链表。可以看到，这个单链表的数据域是val,指针域是next,next存储的是后继结点的地址。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

根据数组生成链表

为了方便讲解对链表的不同操作，我们需要先生成一个链表。在实际应用中，生成链表的方式有很多种，这里简单起见，直接根据一个数组序列来生成一个逻辑顺序相同的链表。这里假设这个数组为[7, 2, 6, 3, 1, 4]。

C++

下面的C++代码先定义了一个长度为6的数组，然后遍历这个数组，依次为数组中的每个元素创建对应的链表结点。当链表为空时，将新建结点的地址赋给head，否则找到最后一个结点，并将新建结点的地址赋给最后一个结点的后继结点。这里需要强调的是head，它不是一个实际的结点，它只是存储了头结点的地址，通过这个head，我们可以找到链表的头结点，进而来操作整个链表。

// 初始化数组，用于生成链表
int a[] = {7, 2, 6, 3, 1, 4};  // 存储待插入的数据
int len = 6;                    // 数组长度

ListNode* head = nullptr;       // 初始化头指针为空

// 使用尾插法构建链表
for (int i = 0; i < len; i++) {
    // 创建新节点，动态分配内存
    ListNode* new_node = new ListNode(a[i]);
    
    // 处理空链表的情况
    if (head == nullptr) {
        head = new_node;    // 如果是空链表，直接将新节点设为头节点
        continue;
    }
    
    // 处理非空链表的情况
    ListNode* p = head;     // 用p遍历链表
    // 找到最后一个节点（尾节点）
    while (p -> next != nullptr) {
        p = p -> next;      // 移动到下一个节点
    }
    p -> next = new_node;   // 将新节点连接到尾节点之后
}

Java

下面的Java代码先定义了一个长度为6的数组，然后遍历这个数组，依次为数组中的每个元素创建对应的链表结点。当链表为空时，将新建结点的地址赋给head，否则找到最后一个结点，并将新建结点的地址赋给最后一个结点的后继结点。

// 初始化数组，用于生成链表
int[] a = {7, 2, 6, 3, 1, 4};  // 存储待插入的数据
int len = 6;                    // 数组长度

ListNode head = null;           // 初始化头指针为空

// 使用尾插法构建链表
for (int i = 0; i < len; i++) {
    // 创建新节点
    ListNode newNode = new ListNode(a[i]);
    
    // 处理空链表的情况
    if (head == null) {         // 如果是空链表
        head = newNode;         // 直接将新节点设为头节点
        continue;
    }
    
    // 处理非空链表的情况
    ListNode p = head;          // 用p遍历链表
    // 找到最后一个节点（尾节点）
    while (p.next != null) {    
        p = p.next;            // 移动到下一个节点
    }
    p.next = newNode;          // 将新节点连接到尾节点之后
}

Python

下面的Python代码先定义了一个长度为6的数组，然后遍历这个数组，依次为数组中的每个元素创建对应的链表结点。当链表为空时，将新建结点的地址赋给head，否则找到最后一个结点，并将新建结点的地址赋给最后一个结点的后继结点。

a = [7, 2, 6, 3, 1, 4]  # 用于生成链表的数组
length = 6  # 数组的长度

head = None  # 链表的头结点

for i in range(length):
    new_node = ListNode(a[i])  # 动态创建节点
    
    # 往链表末尾添加一个结点
    # 如果为空链表，则初始化空链表
    if head is None:
        head = new_node
        continue
    
    # 不为空链表，则遍历到尾结点后加入
    p = head
    while p.next is not None:  
        p = p.next
    p.next = new_node

其它链表

• 对于双链表而言，只需要在单链表的基础上，定义前驱结点的指针域即可；
• 对于单向循环链表，只需要在单链表的基础上，将尾结点的后继结点设置为头结点即可；
• 对于双向循环链表，只需要在双向链表的基础上，将尾结点的后继结点设置为头结点并将首结点的前驱结点设置为尾结点。

链表的遍历

上文中，我们已经可以获得一个完整的链表，那么在实际应用中，我们常常需要遍历链表。下面，给出了遍历链表的示例，同时也可以验证上述构造链表的正确性。

cpp

让p指向头结点，然后不断判断当前指向的结点是否为空，不为空则输出该结点并将p移向后继结点。（输出为：7 2 6 3 1 4 ）

// 遍历并打印链表中的所有元素
ListNode* p = head;           // 从头节点开始遍历
while (p != nullptr) {        // 当前节点不为空时继续遍历
    cout << p -> val << ' '; // 打印当前节点的值
    p = p -> next;           // 移动到下一个节点
}

Java

让p指向头结点，然后不断判断当前指向的结点是否为空，不为空则输出该结点并将p移向后继结点。（输出为：7 2 6 3 1 4 ）

ListNode p = head;
while(p != null) {
    System.out.print(p.val + " ");  
    p = p.next;
}

Python

让p指向头结点，然后不断判断当前指向的结点是否为空，不为空则输出该结点并将p移向后继结点。（输出为：7 2 6 3 1 4 ）

while current:
    print(current.val, end=' ')
    current = current.next

其它链表

在单链表中中，只需要从首结点开始，依次遍历后继结点。

• 对于双链表而言，从前往后遍历和单链表没什么不同，唯一需要注意的是，如果维护了尾结点，双链表可以从后往前遍历。
• 对于单向循环链表而言，可以遍历到尾结点后继续遍历到首结点。

总而言之，你可以从已知结点，根据指针域的情况，依次走到相邻结点。

链表中的插入操作

链表的增加操作可以根据插入的位置不同，分为三种，第一种是插入到链表的头结点之前，第二种是插入到两个元素之间，第三种是插入到最后一个元素之后。下面在代码中给出增加元素的示例。

C++

之前代码生成了一个序列为 7 2 6 3 1 4 的链表，现在我需要依次执行三个操作，第一个操作是往链表头插入一个元素 0并遍历输出链表，第二个操作是在6 和 3 之间插入一个元素 5并遍历输出，第三个操作是在链表尾插入一个元素 10并遍历输出，代码示例如下：

#include <bits/stdc++.h>
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) {}
};

// 遍历输出链表的通用函数
void printList(ListNode* head) {
    ListNode* p = head;
    while (p != nullptr) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

void solve() {
    int a[] = {7, 2, 6, 3, 1, 4};
    int len = 6;
    
    // 原始链表构建（尾插法）
    ListNode* head = nullptr;
    for (int i = 0; i < len; i++) {
        ListNode* new_node = new ListNode(a[i]);
        if (!head) {
            head = new_node;
        } else {
            ListNode* p = head;
            while (p->next) p = p->next;
            p->next = new_node;
        }
    }
    cout << "初始链表: ";
    printList(head);

    // 操作1：头插法插入0
    ListNode* new_head = new ListNode(0, head);
    head = new_head;
    cout << "头插0后: ";
    printList(head);

    // 操作2：在6和3之间插入5
    ListNode* p = head;
    while (p && p->val != 6) p = p->next; // 定位到值为6的节点
    if (p) {
        ListNode* insert_node = new ListNode(5, p->next);
        p->next = insert_node;
    }
    cout << "插入5后: ";
    printList(head);

    // 操作3：尾插法插入10
    ListNode* tail = head;
    while (tail->next) tail = tail->next;
    tail->next = new ListNode(10);
    cout << "尾插10后: ";
    printList(head);
}

int main() {
    solve();
    return 0;
}

Java

之前代码生成了一个序列为 7 2 6 3 1 4 的链表，现在我需要依次执行三个操作，第一个操作是往链表头插入一个元素 0并遍历输出链表，第二个操作是在6 和 3 之间插入一个元素 5并遍历输出，第三个操作是在链表尾插入一个元素 10并遍历输出，代码示例如下：

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int x) { val = x; }
    ListNode(int x, ListNode next) { val = x; this.next = next; }
}

public class Main {
    static void printList(ListNode head) {
        ListNode p = head;
        while (p != null) {
            System.out.print(p.val + " ");
            p = p.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] a = {7, 2, 6, 3, 1, 4};  // 用于生成链表的数组
        int len = 6;                    // 数组的长度
        
        ListNode head = null;            // 链表的头结点

        // 原始链表构建（尾插法）
        for (int i = 0; i < len; i++) {
            ListNode newNode = new ListNode(a[i]);
            
            if (head == null) {          // 空链表初始化
                head = newNode;
                continue;
            }
            
            ListNode p = head;
            while (p.next != null) {    // 遍历到尾节点
                p = p.next;
            }
            p.next = newNode;
        }
        System.out.print("初始链表: ");
        printList(head);

        // 操作1：头插法插入0
        ListNode newHead = new ListNode(0, head);
        head = newHead;
        System.out.print("头插0后: ");
        printList(head);

        // 操作2：在6和3之间插入5
        ListNode p = head;
        while (p != null && p.val != 6) { // 定位到值为6的节点
            p = p.next;
        }
        if (p != null) {
            ListNode insertNode = new ListNode(5, p.next);
            p.next = insertNode;
        }
        System.out.print("插入5后: ");
        printList(head);

        // 操作3：尾插法插入10
        ListNode tail = head;
        while (tail.next != null) {      // 找到尾节点
            tail = tail.next;
        }
        tail.next = new ListNode(10);
        System.out.print("尾插10后: ");
        printList(head);
    }
}

Python

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        """初始化链表节点
        
        Args:
            val: 节点存储的值，默认为0
            next: 指向下一个节点的指针，默认为None
        """
        self.val = val    # 数据域：存储节点的值
        self.next = next  # 指针域：指向下一个节点

def print_list(head):
    """辅助函数：打印链表所有节点的值
    
    Args:
        head: 链表的头节点
    """
    current = head
    while current:        # 当前节点不为空时继续遍历
        print(current.val, end=' ')  # 打印当前节点的值
        current = current.next       # 移动到下一个节点
    print()  # 换行，美化输出格式

def delete_head(head):
    """删除链表的头节点
    
    Args:
        head: 链表的头节点
    Returns:
        删除后的新头节点
    """
    # 处理空链表的情况
    if not head:
        return None
    
    # 直接返回第二个节点作为新的头节点
    # Python会自动进行垃圾回收，不需要手动释放内存
    return head.next

def delete_middle(head, target):
    """删除链表中值为target的节点
    
    Args:
        head: 链表的头节点
        target: 要删除的节点的值
    Returns:
        删除后的链表头节点
    """
    # 处理空链表的情况
    if not head:
        return None
    
    # 特殊情况：如果要删除的是头节点
    if head.val == target:
        return head.next
    
    # 遍历链表寻找目标节点的前驱节点
    current = head
    while current.next and current.next.val != target:
        current = current.next
    
    # 如果找到了目标节点，将其从链表中删除
    if current.next:
        # 让当前节点的next指向目标节点的next，从而跳过目标节点
        current.next = current.next.next
    
    return head

def delete_tail(head):
    """删除链表的尾节点
    
    Args:
        head: 链表的头节点
    Returns:
        删除后的链表头节点
    """
    # 处理空链表和只有一个节点的情况
    if not head or not head.next:
        return None
    
    # 找到倒数第二个节点
    current = head
    while current.next.next:
        current = current.next
    
    # 将倒数第二个节点的next设为None，删除尾节点
    current.next = None
    return head

def main():
    """主函数：演示链表的基本操作"""
    # 构建示例链表：0→7→2→6→5→3→1→4→10
    head = ListNode(0, 
           ListNode(7, 
           ListNode(2, 
           ListNode(6, 
           ListNode(5, 
           ListNode(3, 
           ListNode(1, 
           ListNode(4, 
           ListNode(10)))))))))
    
    # 展示原始链表
    print("原始链表:", end=' ')
    print_list(head)
    
    # 测试删除头节点
    head = delete_head(head)
    print("删除头节点0后:", end=' ')
    print_list(head)  # 输出:7 2 6 5 3 1 4 10
    
    # 测试删除中间节点
    head = delete_middle(head, 5)
    print("删除中间节点5后:", end=' ')
    print_list(head)  # 输出:7 2 6 3 1 4 10
    
    # 测试删除尾节点
    head = delete_tail(head)
    print("删除尾节点10后:", end=' ')
    print_list(head)  # 输出:7 2 6 3 1 4

if __name__ == "__main__":
    main()

关键细节

• 头插法：直接创建新节点指向原头节点，更新head指针即可，时间复杂度O(1)
• 中间插入：需要遍历查找目标节点（时间复杂度O(n)），如插入到目标结点之后，需要将插入结点的后继结点修改为目标结点的后继结点，并将目标结点的后继结点改为插入结点。
• 尾插法：通过遍历找到尾节点后追加（时间复杂度O(n)），若需要优化可维护尾指针
• 内存管理：每次插入使用new动态分配节点内存，实际应用中需注意内存释放（示例未包含释放逻辑）

其它链表

链表结点的插入无非就是维护好插入位置相邻结点的指针情况，一个比较通用的方法就是，先初始化好要插入结点的指针的前驱结点和后继结点，然后再修改后继结点的前驱结点为插入结点，最后修改前驱结点的后继结点为插入结点即可。 这里留作练习，读者可自行实现。

链表的删除操作

链表的删除操作和链表的插入操作其实十分类似，具体而言也可以分为三种，即删除头结点，删除两个结点之间的结点，删除尾结点。前面依次加入了0，5，10，链表序列也从 7 2 6 3 1 4 变成了 0 7 2 6 5 3 1 4 10。那么下面的代码示例就将它变回 7 2 6 3 1 4。

C++

#include <iostream>
using namespace std;

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

void printList(ListNode* head) {
    ListNode* p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

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

ListNode* deleteMiddle(ListNode* head, int target) {
    if (!head) return nullptr;
    ListNode* current = head;
    while (current->next && current->next->val != target) {  // 定位前驱节点
        current = current->next;
    }
    if (current->next) {
        ListNode* temp = current->next;
        current->next = temp->next;
        delete temp;  
    }
    return head;
}

ListNode* deleteTail(ListNode* head) {
    if (!head || !head->next) return nullptr;
    ListNode* current = head;
    while (current->next->next) {  // 定位倒数第二节点
        current = current->next;
    }
    delete current->next; 
    current->next = nullptr;
    return head;
}

void solve() {
    // 构建链表 0→7→2→6→5→3→1→4→10
    ListNode* head = new ListNode(0, 
                        new ListNode(7, 
                        new ListNode(2, 
                        new ListNode(6, 
                        new ListNode(5, 
                        new ListNode(3, 
                        new ListNode(1, 
                        new ListNode(4, 
                        new ListNode(10)))))))));
    
    head = deleteHead(head);
    cout << "删除头节点0后: ";
    printList(head);  // 输出:7 2 6 5 3 1 4 10 

    head = deleteMiddle(head, 5);
    cout << "删除中间节点5后: ";
    printList(head);  // 输出:7 2 6 3 1 4 10 

    head = deleteTail(head);
    cout << "删除尾节点10后: ";
    printList(head);  // 输出:7 2 6 3 1 4 
}

int main() {
    solve();
    return 0;
}

Java

// 定义链表节点类
class ListNode {
    int val;            // 数据域：存储节点的值
    ListNode next;      // 指针域：指向下一个节点
    
    // 构造函数：初始化节点值
    ListNode(int x) { val = x; }
    
    // 构造函数：同时初始化节点值和下一个节点
    ListNode(int x, ListNode next) { val = x; this.next = next; }
}

public class Main {
    /**
     * 辅助方法：打印链表所有节点的值
     * @param head 链表的头节点
     */
    static void printList(ListNode head) {
        ListNode p = head;  // 用于遍历的指针
        while (p != null) {
            System.out.print(p.val + " ");  // 打印当前节点的值
            p = p.next;  // 移动到下一个节点
        }
        System.out.println();  // 换行
    }

    /**
     * 删除链表的头节点
     * @param head 链表的头节点
     * @return 删除后的新头节点
     */
    static ListNode deleteHead(ListNode head) {
        // 处理空链表的情况
        if (head == null) return null;
        
        // 直接返回第二个节点作为新的头节点
        // Java会自动进行垃圾回收，不需要手动释放内存
        return head.next;  
    }

    /**
     * 删除链表中值为target的节点
     * @param head 链表的头节点
     * @param target 要删除的节点的值
     * @return 删除后的链表头节点
     */
    static ListNode deleteMiddle(ListNode head, int target) {
        // 处理空链表的情况
        if (head == null) return null;
        
        // 特殊情况：如果要删除的是头节点
        if (head.val == target) {
            return head.next;
        }
        
        // 遍历链表寻找目标节点的前驱节点
        ListNode current = head;
        while (current.next != null && current.next.val != target) {
            current = current.next;
        }
        
        // 如果找到了目标节点，将其从链表中删除
        if (current.next != null) {
            // 让当前节点的next指向目标节点的next，从而跳过目标节点
            current.next = current.next.next;
        }
        return head;
    }

    /**
     * 删除链表的尾节点
     * @param head 链表的头节点
     * @return 删除后的链表头节点
     */
    static ListNode deleteTail(ListNode head) {
        // 处理空链表和只有一个节点的情况
        if (head == null || head.next == null) return null;
        
        // 找到倒数第二个节点
        ListNode current = head;
        while (current.next.next != null) {
            current = current.next;
        }
        
        // 将倒数第二个节点的next设为null，删除尾节点
        current.next = null;
        return head;
    }

    public static void main(String[] args) {
        // 构建示例链表：0→7→2→6→5→3→1→4→10
        ListNode head = new ListNode(0, 
                        new ListNode(7, 
                        new ListNode(2, 
                        new ListNode(6, 
                        new ListNode(5, 
                        new ListNode(3, 
                        new ListNode(1, 
                        new ListNode(4, 
                        new ListNode(10)))))))));
        
        // 展示原始链表
        System.out.print("原始链表: ");
        printList(head);
        
        // 测试删除头节点
        head = deleteHead(head);
        System.out.print("删除头节点0后: ");
        printList(head);  // 输出:7 2 6 5 3 1 4 10

        // 测试删除中间节点
        head = deleteMiddle(head, 5);
        System.out.print("删除中间节点5后: ");
        printList(head);  // 输出:7 2 6 3 1 4 10

        // 测试删除尾节点
        head = deleteTail(head);
        System.out.print("删除尾节点10后: ");
        printList(head);  // 输出:7 2 6 3 1 4
    }
}

Python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def print_list(head):
    """遍历链表并输出"""
    p = head
    while p:
        print(p.val, end=' ')
        p = p.next
    print()

def delete_head(head):
    """删除头节点"""
    if not head:
        return None
    return head.next  # 直接返回第二个节点作为新头节点

def delete_middle(head, target_val):
    """删除指定值的中间节点"""
    if not head:
        return None
    current = head
    while current.next and current.next.val != target_val:  # 定位前驱节点
        current = current.next
    if current.next:  # 找到目标节点
        current.next = current.next.next  # 跳过目标节点
    return head

def delete_tail(head):
    """删除尾节点"""
    if not head or not head.next:
        return None
    current = head
    while current.next.next:  # 定位到倒数第二个节点
        current = current.next
    current.next = None
    return head

def solve():
    # 原始插入后的链表（0 → 7 → 2 → 6 → 5 → 3 → 1 → 4 → 10）
    head = ListNode(0, ListNode(7, ListNode(2, ListNode(6, ListNode(5, 
              ListNode(3, ListNode(1, ListNode(4, ListNode(10)))))))))

    # 操作1：删除头节点0
    head = delete_head(head)
    print_list(head)  # 输出: 7 2 6 5 3 1 4 10 

    # 操作2：删除中间节点5
    head = delete_middle(head, 5)
    print_list(head)  # 输出: 7 2 6 3 1 4 10 

    # 操作3：删除尾节点10
    head = delete_tail(head)
    print_list(head)  # 输出: 7 2 6 3 1 4 

if __name__ == "__main__":
    solve()

关键细节

• 删除头节点：直接返回原头节点的下一个节点作为新头节点，时间复杂度为O(1)。
• 删除中间节点：通过遍历定位到目标节点的前驱节点（如删除5时，需找到值为6的节点） 调整前驱节点的next指针指向目标节点的下一个节点
• 删除尾节点：遍历到倒数第二个节点（如删除10时，找到值为4的节点），将其next设为None以断开与尾节点的连接 其它链表同理，维护好相邻结点的关系即可。

交换链表相邻的两个元素

假设要交换两个相邻的数组元素十分容易，那么，如何交换链表的两个相邻元素呢？ 假设要交换的两个相邻链表元素分别为 p1 和 p2，p1的前驱结点为pre，p2的后继结点为nxt,那么四个结点的逻辑顺序为 pre，p1，p2，nxt。 那么进行以下三个操作即可完成交换：

• pre 的后继结点设为 p2
• p1 的后继结点设为 nxt
• p2 的后继结点设为p1

if (pre != nullptr) pre->next = p2; 
p1->next = nxt;      // 原头连接后续节点
p2->next = p1;       // 新头连接原头

if (pre != null) pre.next = p2;
p1.next = nxt;
p2.next = p1;

if pre:    # 必须判空，防止 pre 初始为 None
    pre.next = p2
p1.next = nxt      # 原头连接后续
p2.next = p1       # 新头连接原头

例题一:两两交换链表中的结点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路分析

上面已经讲过如何交换两个相邻的链表结点，在该题中，只需要遍历链表，不断维护pre，p1，p2，nxt四个结点，然后对p1和p2进行交换操作即可。

代码实现

class Solution {
public:
    // 两两交换链表中的相邻节点
    // 参数：head - 链表的头节点
    // 返回值：交换后的链表的头节点
    ListNode* swapPairs(ListNode* head) {
        // 处理边界情况：如果链表为空或只有一个节点，直接返回
        if (!head || !head->next) return head;
        
        // 由于要交换第一组节点，新的头节点将是原始链表的第二个节点
        ListNode* result = head->next;
        
        // 初始化四个指针，用于完成节点交换
        ListNode* pre = nullptr;    // 指向待交换的两个节点的前一个节点
        ListNode* p1 = head;        // 指向待交换的第一个节点
        ListNode* p2 = head->next;  // 指向待交换的第二个节点
        ListNode* nxt = p2->next;   // 指向下一组待交换节点的第一个节点
        
        while (true) {
            // 如果不是第一组节点，需要将前一个节点与当前组的第二个节点相连
            if (pre) pre->next = p2;
            
            // 完成一组节点的交换
            p1->next = nxt;     // 第一个节点指向下一组的第一个节点
            p2->next = p1;      // 第二个节点指向第一个节点
            
            // 如果没有更多节点需要交换，退出循环
            if (!nxt || !nxt->next) break;
            
            // 更新四个指针，准备交换下一组节点
            pre = p1;           // 更新前驱节点
            p1 = nxt;           // 更新第一个待交换节点
            p2 = nxt->next;     // 更新第二个待交换节点
            nxt = p2->next;     // 更新下一组的第一个节点
        }
        
        // 返回新的头节点
        return result;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;            // 节点值
 *     ListNode next;      // 指向下一个节点的指针
 *     ListNode() {}       // 默认构造函数
 *     ListNode(int val) { this.val = val; }  // 含参构造函数
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  // 全参构造函数
 * }
 */
class Solution {
    /**
     * 两两交换链表中的相邻节点
     * @param head 链表的头节点
     * @return 交换后的链表的头节点
     */
    public ListNode swapPairs(ListNode head) {
        // 处理边界情况：如果链表为空或只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }
        // 由于要交换第一组节点，新的头节点将是原始链表的第二个节点
        ListNode result = head.next;
        
        // 初始化四个指针，用于完成节点交换
        ListNode pre = null;     // 指向待交换的两个节点的前一个节点
        ListNode p1 = head;      // 指向待交换的第一个节点
        ListNode p2 = head.next; // 指向待交换的第二个节点
        ListNode nxt = head.next.next;  // 指向下一组待交换节点的第一个节点
        
        while (true) {
            // 如果不是第一组节点，需要将前一个节点与当前组的第二个节点相连
            if (pre != null) pre.next = p2;
            // 完成一组节点的交换
            p1.next = nxt;     // 第一个节点指向下一组的第一个节点
            p2.next = p1;      // 第二个节点指向第一个节点
            
            // 如果没有更多节点需要交换，退出循环
            if (nxt == null || nxt.next == null) {
                break;
            }
            
            // 更新四个指针，准备交换下一组节点
            pre = p1;           // 更新前驱节点
            p1 = nxt;           // 更新第一个待交换节点
            p2 = nxt.next;      // 更新第二个待交换节点
            nxt = p2.next;      // 更新下一组的第一个节点
        }
        
        // 返回新的头节点
        return result;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val    # 节点值
#         self.next = next  # 指向下一个节点的指针

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """两两交换链表中的相邻节点
        
        Args:
            head: 链表的头节点
            
        Returns:
            交换后的链表的头节点
        """
        # 处理边界情况：如果链表为空或只有一个节点，直接返回
        if not head or not head.next:
            return head
        
        # 由于要交换第一组节点，新的头节点将是原始链表的第二个节点
        result = head.next
        
        # 初始化四个指针，用于完成节点交换
        pre = None      # 指向待交换的两个节点的前一个节点
        p1 = head       # 指向待交换的第一个节点
        p2 = head.next  # 指向待交换的第二个节点
        nxt = p2.next   # 指向下一组待交换节点的第一个节点
        
        while True:
            # 如果不是第一组节点，需要将前一个节点与当前组的第二个节点相连
            if pre:
                pre.next = p2
            # 完成一组节点的交换
            p1.next = nxt      # 第一个节点指向下一组的第一个节点
            p2.next = p1       # 第二个节点指向第一个节点
 
            # 如果没有更多节点需要交换，退出循环
            if not nxt or not nxt.next:
                break
            
            # 更新四个指针，准备交换下一组节点
            pre = p1            # 更新前驱节点
            p1 = nxt           # 更新第一个待交换节点
            p2 = nxt.next      # 更新第二个待交换节点
            nxt = p2.next      # 更新下一组的第一个节点
        return result

课后习题

习题 1：移除链表元素 习题 2：反转链表 习题 3：链表序列化 习题 4：序列链表化 习题 5：合并两个排序的链表 习题 6：判断一个链表是否为回文结构 习题 7：插队