数据结构之链表详解

1. 引言

链表是计算机科学中最基础、最重要的数据结构之一，它是一种线性数据结构，但与数组不同，链表中的元素在内存中并不是连续存储的。链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。这种非连续存储的特性使得链表在插入和删除操作上具有很高的效率。

链表的概念最早可以追溯到1955年，由Allen Newell、Cliff Shaw和Herbert A. Simon在开发信息处理语言（IPL）时提出。随着计算机科学的发展，链表已经成为各种编程语言和系统设计中不可或缺的基础数据结构。

在实际应用中，链表被广泛用于实现文件系统、内存管理、哈希表的链地址法、LRU缓存淘汰算法等。理解链表的原理和实现对于提高编程能力和解决复杂问题至关重要。

2. 链表的基本概念

2.1 链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点（node）组成，每个节点包含两个部分：

  • 数据域：存储数据元素
  • 指针域：存储指向下一个节点的指针
// 链表节点的基本结构
struct ListNode {
    int data;           // 数据域
    struct ListNode *next; // 指针域，指向下一个节点
};

2.2 链表与数组的对比

为了更好地理解链表的特性，我们将其与数组进行对比：

特性 数组 链表
内存分配 连续内存块 非连续内存，动态分配
大小 固定大小 动态大小，可随时扩展
插入/删除效率 O(n) O(1)（已知位置时）
随机访问效率 O(1) O(n)
内存利用率 可能浪费或不足 按需分配，无浪费
缓存友好性 好（空间局部性） 差

2.3 链表的专业术语

  • 节点（Node）：链表的基本单位
  • 头节点（Head）：链表的第一个节点
  • 尾节点（Tail）：链表的最后一个节点
  • 空链表：不包含任何节点的链表
  • 单向链表：每个节点只有一个指向后继的指针
  • 双向链表：每个节点有指向前驱和后继的两个指针
  • 循环链表：尾节点指向头节点的链表

3. 链表的分类

3.1 单向链表

单向链表是最简单的链表形式，每个节点只有一个指向下一个节点的指针。

#include <stdio.h>
#include <stdlib.h>

// 单向链表节点定义
typedef struct SinglyListNode {
    int data;
    struct SinglyListNode *next;
} SinglyListNode;

// 创建新节点
SinglyListNode* createSinglyNode(int data) {
    SinglyListNode* newNode = (SinglyListNode*)malloc(sizeof(SinglyListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表头部插入节点
void insertAtHead(SinglyListNode** head, int data) {
    SinglyListNode* newNode = createSinglyNode(data);
    newNode->next = *head;
    *head = newNode;
}

// 在链表尾部插入节点
void insertAtTail(SinglyListNode** head, int data) {
    SinglyListNode* newNode = createSinglyNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    SinglyListNode* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

// 打印链表
void printSinglyList(SinglyListNode* head) {
    SinglyListNode* current = head;
    printf("链表: ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 删除节点
void deleteNode(SinglyListNode** head, int key) {
    SinglyListNode *temp = *head, *prev = NULL;
    
    // 如果要删除的是头节点
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    
    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    
    // 如果没找到
    if (temp == NULL) return;
    
    // 从链表中解除节点
    prev->next = temp->next;
    free(temp);
}

// 查找节点
SinglyListNode* searchNode(SinglyListNode* head, int key) {
    SinglyListNode* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

3.2 双向链表

双向链表的每个节点有两个指针，分别指向前一个节点和后一个节点。

#include <stdio.h>
#include <stdlib.h>

// 双向链表节点定义
typedef struct DoublyListNode {
    int data;
    struct DoublyListNode *prev;
    struct DoublyListNode *next;
} DoublyListNode;

// 创建新节点
DoublyListNode* createDoublyNode(int data) {
    DoublyListNode* newNode = (DoublyListNode*)malloc(sizeof(DoublyListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 在头部插入节点
void insertAtHead(DoublyListNode** head, int data) {
    DoublyListNode* newNode = createDoublyNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    newNode->next = *head;
    (*head)->prev = newNode;
    *head = newNode;
}

// 在尾部插入节点
void insertAtTail(DoublyListNode** head, int data) {
    DoublyListNode* newNode = createDoublyNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    DoublyListNode* current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
    newNode->prev = current;
}

// 在指定位置插入节点
void insertAfter(DoublyListNode* prevNode, int data) {
    if (prevNode == NULL) {
        printf("前一个节点不能为NULL\n");
        return;
    }
    
    DoublyListNode* newNode = createDoublyNode(data);
    
    newNode->next = prevNode->next;
    newNode->prev = prevNode;
    
    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    
    prevNode->next = newNode;
}

// 删除节点
void deleteDoublyNode(DoublyListNode** head, DoublyListNode* delNode) {
    if (*head == NULL || delNode == NULL) return;
    
    // 如果要删除的是头节点
    if (*head == delNode) {
        *head = delNode->next;
    }
    
    // 如果删除的不是最后一个节点
    if (delNode->next != NULL) {
        delNode->next->prev = delNode->prev;
    }
    
    // 如果删除的不是第一个节点
    if (delNode->prev != NULL) {
        delNode->prev->next = delNode->next;
    }
    
    free(delNode);
}

// 向前打印链表
void printForward(DoublyListNode* head) {
    DoublyListNode* current = head;
    printf("向前遍历: ");
    while (current != NULL) {
        printf("%d <-> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

// 向后打印链表
void printBackward(DoublyListNode* head) {
    if (head == NULL) return;
    
    // 先找到尾节点
    DoublyListNode* tail = head;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    
    printf("向后遍历: ");
    while (tail != NULL) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
    printf("NULL\n");
}

3.3 循环链表

循环链表是一种特殊的链表，其中尾节点指向头节点，形成一个环。

#include <stdio.h>
#include <stdlib.h>

// 循环链表节点定义
typedef struct CircularListNode {
    int data;
    struct CircularListNode *next;
} CircularListNode;

// 创建新节点
CircularListNode* createCircularNode(int data) {
    CircularListNode* newNode = (CircularListNode*)malloc(sizeof(CircularListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到循环链表
void insertCircularNode(CircularListNode** head, int data) {
    CircularListNode* newNode = createCircularNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode; // 指向自己形成环
        return;
    }
    
    CircularListNode* current = *head;
    
    // 找到尾节点（尾节点的next指向头节点）
    while (current->next != *head) {
        current = current->next;
    }
    
    current->next = newNode;
    newNode->next = *head;
}

// 打印循环链表
void printCircularList(CircularListNode* head) {
    if (head == NULL) {
        printf("空链表\n");
        return;
    }
    
    CircularListNode* current = head;
    printf("循环链表: ");
    
    do {
        printf("%d -> ", current->data);
        current = current->next;
    } while (current != head);
    
    printf("(头节点)\n");
}

// 删除循环链表中的节点
void deleteCircularNode(CircularListNode** head, int key) {
    if (*head == NULL) return;
    
    CircularListNode *current = *head, *prev = NULL;
    
    // 如果头节点就是要删除的节点
    if (current->data == key) {
        // 如果只有一个节点
        if (current->next == *head) {
            free(current);
            *head = NULL;
            return;
        }
        
        // 找到尾节点
        CircularListNode* tail = *head;
        while (tail->next != *head) {
            tail = tail->next;
        }
        
        tail->next = (*head)->next;
        CircularListNode* temp = *head;
        *head = (*head)->next;
        free(temp);
        return;
    }
    
    // 查找要删除的节点
    do {
        prev = current;
        current = current->next;
    } while (current != *head && current->data != key);
    
    // 如果找到要删除的节点
    if (current != *head) {
        prev->next = current->next;
        free(current);
    }
}

3.4 双向循环链表

双向循环链表结合了双向链表和循环链表的特性。

#include <stdio.h>
#include <stdlib.h>

// 双向循环链表节点定义
typedef struct DoublyCircularListNode {
    int data;
    struct DoublyCircularListNode *prev;
    struct DoublyCircularListNode *next;
} DoublyCircularListNode;

// 创建新节点
DoublyCircularListNode* createDoublyCircularNode(int data) {
    DoublyCircularListNode* newNode = (DoublyCircularListNode*)malloc(sizeof(DoublyCircularListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到双向循环链表
void insertDoublyCircularNode(DoublyCircularListNode** head, int data) {
    DoublyCircularListNode* newNode = createDoublyCircularNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        newNode->prev = newNode;
        newNode->next = newNode;
        return;
    }
    
    DoublyCircularListNode* tail = (*head)->prev;
    
    tail->next = newNode;
    newNode->prev = tail;
    newNode->next = *head;
    (*head)->prev = newNode;
}

// 打印双向循环链表
void printDoublyCircularList(DoublyCircularListNode* head) {
    if (head == NULL) {
        printf("空链表\n");
        return;
    }
    
    DoublyCircularListNode* current = head;
    printf("双向循环链表(向前): ");
    
    do {
        printf("%d <-> ", current->data);
        current = current->next;
    } while (current != head);
    
    printf("(头节点)\n");
    
    printf("双向循环链表(向后): ");
    current = head->prev;
    
    do {
        printf("%d <-> ", current->data);
        current = current->prev;
    } while (current != head->prev);
    
    printf("(尾节点)\n");
}

4. 链表的基本操作

4.1 创建和初始化链表

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建空链表
Node* createEmptyList() {
    return NULL;
}

// 创建带头节点的链表
Node* createListWithHead() {
    Node* head = (Node*)malloc(sizeof(Node));
    if (head == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    head->next = NULL;
    return head;
}

// 从数组创建链表
Node* createListFromArray(int arr[], int size) {
    if (size == 0) return NULL;
    
    Node* head = createNode(arr[0]);
    Node* current = head;
    
    for (int i = 1; i < size; i++) {
        current->next = createNode(arr[i]);
        current = current->next;
    }
    
    return head;
}

4.2 遍历链表

// 遍历链表并打印元素
void traverseList(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return;
    }
    
    Node* current = head;
    int position = 0;
    
    printf("链表元素: ");
    while (current != NULL) {
        printf("[%d]:%d", position, current->data);
        if (current->next != NULL) {
            printf(" -> ");
        }
        current = current->next;
        position++;
    }
    printf("\n");
}

// 获取链表长度
int getLength(Node* head) {
    int length = 0;
    Node* current = head;
    
    while (current != NULL) {
        length++;
        current = current->next;
    }
    
    return length;
}

// 递归方式遍历链表
void traverseRecursive(Node* head) {
    if (head == NULL) {
        return;
    }
    
    printf("%d ", head->data);
    traverseRecursive(head->next);
}

4.3 插入操作

// 在链表头部插入
Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = createNode(data);
    newNode->next = head;
    return newNode;
}

// 在链表尾部插入
Node* insertAtEnd(Node* head, int data) {
    Node* newNode = createNode(data);
    
    if (head == NULL) {
        return newNode;
    }
    
    Node* current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    
    current->next = newNode;
    return head;
}

// 在指定位置插入
Node* insertAtPosition(Node* head, int data, int position) {
    if (position < 0) {
        printf("位置不能为负数\n");
        return head;
    }
    
    if (position == 0) {
        return insertAtBeginning(head, data);
    }
    
    Node* newNode = createNode(data);
    Node* current = head;
    int currentPosition = 0;
    
    // 找到要插入位置的前一个节点
    while (current != NULL && currentPosition < position - 1) {
        current = current->next;
        currentPosition++;
    }
    
    if (current == NULL) {
        printf("位置超出链表长度\n");
        free(newNode);
        return head;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    
    return head;
}

// 在有序链表中插入（保持有序）
Node* insertInSortedList(Node* head, int data) {
    Node* newNode = createNode(data);
    
    // 如果链表为空或新节点应该放在头部
    if (head == NULL || data < head->data) {
        newNode->next = head;
        return newNode;
    }
    
    Node* current = head;
    
    // 找到插入位置
    while (current->next != NULL && current->next->data < data) {
        current = current->next;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    
    return head;
}

4.4 删除操作

// 删除头节点
Node* deleteFromBeginning(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return NULL;
    }
    
    Node* temp = head;
    head = head->next;
    free(temp);
    return head;
}

// 删除尾节点
Node* deleteFromEnd(Node* head) {
    if (head == NULL) {
        printf("链表为空\n");
        return NULL;
    }
    
    if (head->next == NULL) {
        // 只有一个节点
        free(head);
        return NULL;
    }
    
    Node* current = head;
    
    // 找到倒数第二个节点
    while (current->next->next != NULL) {
        current = current->next;
    }
    
    free(current->next);
    current->next = NULL;
    
    return head;
}

// 删除指定值的节点
Node* deleteByValue(Node* head, int value) {
    if (head == NULL) {
        printf("链表为空\n");
        return NULL;
    }
    
    // 如果要删除的是头节点
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }
    
    Node* current = head;
    
    // 找到要删除节点的前一个节点
    while (current->next != NULL && current->next->data != value) {
        current = current->next;
    }
    
    if (current->next == NULL) {
        printf("未找到值为 %d 的节点\n", value);
        return head;
    }
    
    Node* temp = current->next;
    current->next = current->next->next;
    free(temp);
    
    return head;
}

// 删除指定位置的节点
Node* deleteByPosition(Node* head, int position) {
    if (head == NULL) {
        printf("链表为空\n");
        return NULL;
    }
    
    if (position == 0) {
        return deleteFromBeginning(head);
    }
    
    Node* current = head;
    int currentPosition = 0;
    
    // 找到要删除位置的前一个节点
    while (current != NULL && currentPosition < position - 1) {
        current = current->next;
        currentPosition++;
    }
    
    if (current == NULL || current->next == NULL) {
        printf("位置超出链表长度\n");
        return head;
    }
    
    Node* temp = current->next;
    current->next = current->next->next;
    free(temp);
    
    return head;
}

4.5 查找和更新操作

// 查找节点是否存在
int searchNode(Node* head, int value) {
    Node* current = head;
    int position = 0;
    
    while (current != NULL) {
        if (current->data == value) {
            return position;
        }
        current = current->next;
        position++;
    }
    
    return -1; // 未找到
}

// 获取指定位置的节点值
int getValueAtPosition(Node* head, int position) {
    if (position < 0) {
        printf("位置不能为负数\n");
        return -1;
    }
    
    Node* current = head;
    int currentPosition = 0;
    
    while (current != NULL && currentPosition < position) {
        current = current->next;
        currentPosition++;
    }
    
    if (current == NULL) {
        printf("位置超出链表长度\n");
        return -1;
    }
    
    return current->data;
}

// 更新指定位置的节点值
void updateValueAtPosition(Node* head, int position, int newValue) {
    if (position < 0) {
        printf("位置不能为负数\n");
        return;
    }
    
    Node* current = head;
    int currentPosition = 0;
    
    while (current != NULL && currentPosition < position) {
        current = current->next;
        currentPosition++;
    }
    
    if (current == NULL) {
        printf("位置超出链表长度\n");
        return;
    }
    
    current->data = newValue;
}

// 查找中间节点（快慢指针法）
Node* findMiddleNode(Node* head) {
    if (head == NULL) return NULL;
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

5. 高级链表算法

5.1 链表反转

// 迭代法反转链表
Node* reverseListIterative(Node* head) {
    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;
    
    while (current != NULL) {
        next = current->next; // 保存下一个节点
        current->next = prev; // 反转指针
        prev = current;       // 移动prev
        current = next;       // 移动current
    }
    
    return prev; // 新的头节点
}

// 递归法反转链表
Node* reverseListRecursive(Node* head) {
    // 基本情况：空链表或只有一个节点
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 递归反转剩余部分
    Node* newHead = reverseListRecursive(head->next);
    
    // 反转当前节点
    head->next->next = head;
    head->next = NULL;
    
    return newHead;
}

// 反转部分链表（从位置m到n）
Node* reverseBetween(Node* head, int m, int n) {
    if (head == NULL || m == n) return head;
    
    Node* dummy = createNode(0); // 虚拟头节点
    dummy->next = head;
    
    Node* pre = dummy;
    
    // 移动到第m-1个节点
    for (int i = 1; i < m; i++) {
        pre = pre->next;
    }
    
    Node* start = pre->next;
    Node* then = start->next;
    
    // 反转m到n的部分
    for (int i = 0; i < n - m; i++) {
        start->next = then->next;
        then->next = pre->next;
        pre->next = then;
        then = start->next;
    }
    
    Node* result = dummy->next;
    free(dummy);
    return result;
}

5.2 链表排序

// 合并两个有序链表
Node* mergeSortedLists(Node* l1, Node* l2) {
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;
    
    Node* dummy = createNode(0);
    Node* current = dummy;
    
    while (l1 != NULL && l2 != NULL) {
        if (l1->data <= l2->data) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }
    
    // 连接剩余部分
    if (l1 != NULL) {
        current->next = l1;
    } else {
        current->next = l2;
    }
    
    Node* result = dummy->next;
    free(dummy);
    return result;
}

// 归并排序链表
Node* mergeSort(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 找到中间节点
    Node* slow = head;
    Node* fast = head->next;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 分割链表
    Node* mid = slow->next;
    slow->next = NULL;
    
    // 递归排序
    Node* left = mergeSort(head);
    Node* right = mergeSort(mid);
    
    // 合并
    return mergeSortedLists(left, right);
}

// 插入排序链表
Node* insertionSortList(Node* head) {
    if (head == NULL || head->next == NULL) return head;
    
    Node* dummy = createNode(0); // 虚拟头节点
    Node* current = head;
    
    while (current != NULL) {
        Node* next = current->next;
        Node* prev = dummy;
        
        // 在已排序部分找到插入位置
        while (prev->next != NULL && prev->next->data < current->data) {
            prev = prev->next;
        }
        
        // 插入当前节点
        current->next = prev->next;
        prev->next = current;
        
        current = next;
    }
    
    Node* result = dummy->next;
    free(dummy);
    return result;
}

5.3 环检测和环入口查找

// 检测链表是否有环（快慢指针法）
int hasCycle(Node* head) {
    if (head == NULL || head->next == NULL) {
        return 0;
    }
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return 1; // 有环
        }
    }
    
    return 0; // 无环
}

// 找到环的入口节点
Node* detectCycle(Node* head) {
    if (head == NULL || head->next == NULL) {
        return NULL;
    }
    
    Node* slow = head;
    Node* fast = head;
    int hasCycle = 0;
    
    // 检测环
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            hasCycle = 1;
            break;
        }
    }
    
    if (!hasCycle) {
        return NULL;
    }
    
    // 找到环的入口
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    
    return slow;
}

// 计算环的长度
int cycleLength(Node* head) {
    Node* meetingPoint = detectCycle(head);
    if (meetingPoint == NULL) {
        return 0; // 无环
    }
    
    Node* current = meetingPoint->next;
    int length = 1;
    
    while (current != meetingPoint) {
        current = current->next;
        length++;
    }
    
    return length;
}

5.4 链表相交问题

// 获取链表长度
int getListLength(Node* head) {
    int length = 0;
    Node* current = head;
    
    while (current != NULL) {
        length++;
        current = current->next;
    }
    
    return length;
}

// 找到两个链表的交点
Node* getIntersectionNode(Node* headA, Node* headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    
    int lenA = getListLength(headA);
    int lenB = getListLength(headB);
    
    Node* longList = (lenA >= lenB) ? headA : headB;
    Node* shortList = (lenA >= lenB) ? headB : headA;
    
    int diff = abs(lenA - lenB);
    
    // 长链表先走diff步
    for (int i = 0; i < diff; i++) {
        longList = longList->next;
    }
    
    // 同时前进直到找到交点或到达末尾
    while (longList != NULL && shortList != NULL) {
        if (longList == shortList) {
            return longList;
        }
        longList = longList->next;
        shortList = shortList->next;
    }
    
    return NULL;
}

// 另一种方法：双指针法
Node* getIntersectionNodeTwoPointers(Node* headA, Node* headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    
    Node* pA = headA;
    Node* pB = headB;
    
    while (pA != pB) {
        pA = (pA == NULL) ? headB : pA->next;
        pB = (pB == NULL) ? headA : pB->next;
    }
    
    return pA;
}

6. 特殊链表问题

6.1 回文链表判断

// 方法1：反转后半部分比较
int isPalindrome(Node* head) {
    if (head == NULL || head->next == NULL) {
        return 1;
    }
    
    // 找到中间节点
    Node* slow = head;
    Node* fast = head;
    
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 反转后半部分
    Node* secondHalf = reverseListIterative(slow->next);
    Node* firstHalf = head;
    
    // 比较两部分
    Node* temp = secondHalf;
    int result = 1;
    
    while (temp != NULL) {
        if (firstHalf->data != temp->data) {
            result = 0;
            break;
        }
        firstHalf = firstHalf->next;
        temp = temp->next;
    }
    
    // 恢复链表
    reverseListIterative(secondHalf);
    
    return result;
}

// 方法2：使用栈
#include <stdlib.h>
#define MAX_SIZE 1000

typedef struct Stack {
    int data[MAX_SIZE];
    int top;
} Stack;

void initStack(Stack* s) {
    s->top = -1;
}

void push(Stack* s, int value) {
    if (s->top < MAX_SIZE - 1) {
        s->data[++(s->top)] = value;
    }
}

int pop(Stack* s) {
    if (s->top >= 0) {
        return s->data[(s->top)--];
    }
    return -1;
}

int isPalindromeWithStack(Node* head) {
    if (head == NULL || head->next == NULL) {
        return 1;
    }
    
    Stack s;
    initStack(&s);
    
    Node* current = head;
    int length = 0;
    
    // 将链表元素压入栈中并计算长度
    while (current != NULL) {
        push(&s, current->data);
        current = current->next;
        length++;
    }
    
    current = head;
    
    // 比较栈中元素和链表元素
    for (int i = 0; i < length / 2; i++) {
        if (current->data != pop(&s)) {
            return 0;
        }
        current = current->next;
    }
    
    return 1;
}

6.2 重排链表

// 重排链表：L0→Ln→L1→Ln-1→L2→Ln-2→...
void reorderList(Node* head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    
    // 找到中间节点
    Node* slow = head;
    Node* fast = head;
    
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    // 反转后半部分
    Node* secondHalf = reverseListIterative(slow->next);
    slow->next = NULL;
    
    // 合并两个链表
    Node* firstHalf = head;
    
    while (secondHalf != NULL) {
        Node* temp1 = firstHalf->next;
        Node* temp2 = secondHalf->next;
        
        firstHalf->next = secondHalf;
        secondHalf->next = temp1;
        
        firstHalf = temp1;
        secondHalf = temp2;
    }
}

6.3 奇偶链表

// 将奇数位置的节点放在前面，偶数位置的节点放在后面
Node* oddEvenList(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    Node* odd = head;
    Node* even = head->next;
    Node* evenHead = even;
    
    while (even != NULL && even->next != NULL) {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    
    odd->next = evenHead;
    return head;
}

7. 实际应用案例

7.1 LRU缓存实现

#include <stdio.h>
#include <stdlib.h>

#define CACHE_CAPACITY 5

// LRU缓存节点
typedef struct LRUNode {
    int key;
    int value;
    struct LRUNode* prev;
    struct LRUNode* next;
} LRUNode;

// LRU缓存结构
typedef struct {
    int capacity;
    int size;
    LRUNode* head;
    LRUNode* tail;
    LRUNode** hashMap; // 简化版，实际应该用哈希表
} LRUCache;

// 创建LRU节点
LRUNode* createLRUNode(int key, int value) {
    LRUNode* node = (LRUNode*)malloc(sizeof(LRUNode));
    node->key = key;
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 初始化LRU缓存
LRUCache* createLRUCache(int capacity) {
    LRUCache* cache = (LRUCache*)malloc(sizeof(LRUCache));
    cache->capacity = capacity;
    cache->size = 0;
    cache->head = createLRUNode(-1, -1); // 虚拟头节点
    cache->tail = createLRUNode(-1, -1); // 虚拟尾节点
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;
    
    // 简化版哈希表，实际应该用真正的哈希表实现
    cache->hashMap = (LRUNode**)calloc(1000, sizeof(LRUNode*));
    
    return cache;
}

// 将节点移到头部（表示最近使用）
void moveToHead(LRUCache* cache, LRUNode* node) {
    // 从原位置移除
    if (node->prev != NULL) {
        node->prev->next = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }
    
    // 插入到头部
    node->next = cache->head->next;
    node->prev = cache->head;
    cache->head->next->prev = node;
    cache->head->next = node;
}

// 移除尾部节点（最久未使用）
void removeTail(LRUCache* cache) {
    if (cache->size == 0) return;
    
    LRUNode* tailNode = cache->tail->prev;
    tailNode->prev->next = cache->tail;
    cache->tail->prev = tailNode->prev;
    
    // 从哈希表中移除
    cache->hashMap[tailNode->key] = NULL;
    free(tailNode);
    cache->size--;
}

// 获取缓存值
int get(LRUCache* cache, int key) {
    LRUNode* node = cache->hashMap[key];
    if (node == NULL) {
        return -1; // 未找到
    }
    
    // 移到头部表示最近使用
    moveToHead(cache, node);
    return node->value;
}

// 插入缓存值
void put(LRUCache* cache, int key, int value) {
    LRUNode* node = cache->hashMap[key];
    
    if (node != NULL) {
        // 键已存在，更新值并移到头部
        node->value = value;
        moveToHead(cache, node);
    } else {
        // 创建新节点
        node = createLRUNode(key, value);
        cache->hashMap[key] = node;
        
        // 插入到头部
        node->next = cache->head->next;
        node->prev = cache->head;
        cache->head->next->prev = node;
        cache->head->next = node;
        cache->size++;
        
        // 如果超出容量，移除尾部节点
        if (cache->size > cache->capacity) {
            removeTail(cache);
        }
    }
}

// 打印LRU缓存
void printLRUCache(LRUCache* cache) {
    printf("LRU缓存内容: ");
    LRUNode* current = cache->head->next;
    while (current != cache->tail) {
        printf("(%d:%d) ", current->key, current->value);
        current = current->next;
    }
    printf("\n");
}

7.2 多项式相加

#include <stdio.h>
#include <stdlib.h>

// 多项式节点
typedef struct PolyNode {
    int coeff;  // 系数
    int exp;    // 指数
    struct PolyNode* next;
} PolyNode;

// 创建多项式节点
PolyNode* createPolyNode(int coeff, int exp) {
    PolyNode* node = (PolyNode*)malloc(sizeof(PolyNode));
    node->coeff = coeff;
    node->exp = exp;
    node->next = NULL;
    return node;
}

// 添加项到多项式
void addTerm(PolyNode** poly, int coeff, int exp) {
    PolyNode* newNode = createPolyNode(coeff, exp);
    
    if (*poly == NULL) {
        *poly = newNode;
        return;
    }
    
    PolyNode* current = *poly;
    PolyNode* prev = NULL;
    
    // 按指数降序插入
    while (current != NULL && current->exp > exp) {
        prev = current;
        current = current->next;
    }
    
    // 如果指数相同，合并系数
    if (current != NULL && current->exp == exp) {
        current->coeff += coeff;
        free(newNode);
        return;
    }
    
    // 插入新节点
    newNode->next = current;
    if (prev == NULL) {
        *poly = newNode;
    } else {
        prev->next = newNode;
    }
}

// 多项式相加
PolyNode* addPolynomials(PolyNode* poly1, PolyNode* poly2) {
    PolyNode* result = NULL;
    PolyNode* p1 = poly1;
    PolyNode* p2 = poly2;
    
    while (p1 != NULL && p2 != NULL) {
        if (p1->exp == p2->exp) {
            addTerm(&result, p1->coeff + p2->coeff, p1->exp);
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            addTerm(&result, p1->coeff, p1->exp);
            p1 = p1->next;
        } else {
            addTerm(&result, p2->coeff, p2->exp);
            p2 = p2->next;
        }
    }
    
    // 处理剩余部分
    while (p1 != NULL) {
        addTerm(&result, p1->coeff, p1->exp);
        p1 = p1->next;
    }
    
    while (p2 != NULL) {
        addTerm(&result, p2->coeff, p2->exp);
        p2 = p2->next;
    }
    
    return result;
}

// 打印多项式
void printPolynomial(PolyNode* poly) {
    if (poly == NULL) {
        printf("0\n");
        return;
    }
    
    PolyNode* current = poly;
    int firstTerm = 1;
    
    while (current != NULL) {
        if (current->coeff != 0) {
            if (!firstTerm && current->coeff > 0) {
                printf(" + ");
            }
            
            if (current->exp == 0) {
                printf("%d", current->coeff);
            } else if (current->exp == 1) {
                printf("%dx", current->coeff);
            } else {
                printf("%dx^%d", current->coeff, current->exp);
            }
            
            firstTerm = 0;
        }
        current = current->next;
    }
    printf("\n");
}

8. 性能分析和优化

8.1 时间复杂度分析

操作 数组 链表
访问 O(1) O(n)
插入（头部） O(n) O(1)
插入（尾部） O(1)（已知位置） O(1)（有尾指针）
插入（中间） O(n) O(1)（已知位置）
删除（头部） O(n) O(1)
删除（尾部） O(1) O(n)（单向链表）
删除（中间） O(n) O(1)（已知位置）
查找 O(n) O(n)

8.2 空间复杂度分析

  • 数组：需要连续的内存空间，可能造成内存浪费或不足
  • 链表：每个节点需要额外的指针空间，但可以动态分配，无内存浪费

8.3 缓存性能

由于现代计算机系统的缓存机制，连续内存访问（数组）通常比随机内存访问（链表）具有更好的性能。这就是为什么在实际应用中，数组通常比链表更快，尽管某些操作的时间复杂度相同。

8.4 优化技巧

  1. 使用双向链表：对于需要频繁前后遍历的场景
  2. 维护尾指针：加速尾部操作
  3. 使用哨兵节点：简化边界条件处理
  4. 内存池：预分配节点，减少malloc/free开销
  5. 缓存友好设计：尽量让相关数据在内存中连续存储
// 使用内存池优化链表
#define POOL_SIZE 1000

typedef struct NodePool {
    Node nodes[POOL_SIZE];
    int used;
    struct NodePool* next;
} NodePool;

NodePool* createNodePool() {
    NodePool* pool = (NodePool*)malloc(sizeof(NodePool));
    pool->used = 0;
    pool->next = NULL;
    return pool;
}

Node* allocateNode(NodePool** pool, int data) {
    if ((*pool)->used >= POOL_SIZE) {
        // 创建新的内存池
        NodePool* newPool = createNodePool();
        newPool->next = *pool;
        *pool = newPool;
    }
    
    Node* node = &((*pool)->nodes[(*pool)->used]);
    node->data = data;
    node->next = NULL;
    (*pool)->used++;
    
    return node;
}

9. 常见面试题解析

9.1 反转链表系列

// 递归反转链表（详细注释版）
Node* reverseListRecursiveDetailed(Node* head) {
    // 基本情况：空链表或只有一个节点，无需反转
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 递归反转剩余部分，返回新的头节点
    Node* newHead = reverseListRecursiveDetailed(head->next);
    
    // 关键步骤：将当前节点的下一个节点的next指针指向当前节点
    // 这样就实现了局部的反转
    head->next->next = head;
    
    // 将当前节点的next设为NULL，防止形成环
    head->next = NULL;
    
    // 返回新的头节点
    return newHead;
}

// K个一组反转链表
Node* reverseKGroup(Node* head, int k) {
    if (head == NULL || k == 1) return head;
    
    Node* dummy = createNode(0);
    dummy->next = head;
    
    Node *pre = dummy, *cur = dummy, *nex = dummy;
    int count = 0;
    
    // 计算链表长度
    while (cur->next != NULL) {
        cur = cur->next;
        count++;
    }
    
    while (count >= k) {
        cur = pre->next;
        nex = cur->next;
        
        // 反转k个节点
        for (int i = 1; i < k; i++) {
            cur->next = nex->next;
            nex->next = pre->next;
            pre->next = nex;
            nex = cur->next;
        }
        
        pre = cur;
        count -= k;
    }
    
    Node* result = dummy->next;
    free(dummy);
    return result;
}

9.2 链表排序系列

// 快速排序链表
Node* partition(Node* head, Node* end, Node** newHead, Node** newEnd) {
    Node* pivot = end;
    Node* prev = NULL;
    Node* cur = head;
    Node* tail = pivot;
    
    while (cur != pivot) {
        if (cur->data < pivot->data) {
            if (*newHead == NULL) {
                *newHead = cur;
            }
            prev = cur;
            cur = cur->next;
        } else {
            if (prev) {
                prev->next = cur->next;
            }
            Node* temp = cur->next;
            cur->next = NULL;
            tail->next = cur;
            tail = cur;
            cur = temp;
        }
    }
    
    if (*newHead == NULL) {
        *newHead = pivot;
    }
    
    *newEnd = tail;
    return pivot;
}

Node* quickSortRecursive(Node* head, Node* end) {
    if (!head || head == end) return head;
    
    Node* newHead = NULL;
    Node* newEnd = NULL;
    
    Node* pivot = partition(head, end, &newHead, &newEnd);
    
    if (newHead != pivot) {
        Node* temp = newHead;
        while (temp->next != pivot) {
            temp = temp->next;
        }
        temp->next = NULL;
        
        newHead = quickSortRecursive(newHead, temp);
        
        temp = getTail(newHead);
        temp->next = pivot;
    }
    
    pivot->next = quickSortRecursive(pivot->next, newEnd);
    
    return newHead;
}

Node* quickSort(Node* head) {
    Node* tail = getTail(head);
    return quickSortRecursive(head, tail);
}

9.3 深度拷贝带随机指针的链表

#include <stdio.h>
#include <stdlib.h>

typedef struct RandomListNode {
    int data;
    struct RandomListNode* next;
    struct RandomListNode* random;
} RandomListNode;

RandomListNode* createRandomNode(int data) {
    RandomListNode* node = (RandomListNode*)malloc(sizeof(RandomListNode));
    node->data = data;
    node->next = NULL;
    node->random = NULL;
    return node;
}

// 深度拷贝带随机指针的链表
RandomListNode* copyRandomList(RandomListNode* head) {
    if (head == NULL) return NULL;
    
    RandomListNode* current = head;
    
    // 第一步：在每个原节点后面插入拷贝节点
    while (current != NULL) {
        RandomListNode* copy = createRandomNode(current->data);
        copy->next = current->next;
        current->next = copy;
        current = copy->next;
    }
    
    // 第二步：设置random指针
    current = head;
    while (current != NULL) {
        if (current->random != NULL) {
            current->next->random = current->random->next;
        }
        current = current->next->next;
    }
    
    // 第三步：分离两个链表
    current = head;
    RandomListNode* copyHead = head->next;
    RandomListNode* copyCurrent = copyHead;
    
    while (current != NULL) {
        current->next = current->next->next;
        if (copyCurrent->next != NULL) {
            copyCurrent->next = copyCurrent->next->next;
        }
        current = current->next;
        copyCurrent = copyCurrent->next;
    }
    
    return copyHead;
}

10. 总结

链表作为一种基础而重要的数据结构，在计算机科学中有着广泛的应用。通过本文的详细讲解，我们应该掌握：

10.1 链表的优缺点

优点：

  • 动态大小，无需预先分配内存
  • 插入和删除操作高效
  • 内存利用率高，无碎片问题

缺点：

  • 随机访问效率低
  • 需要额外的指针空间
  • 缓存不友好
  • 实现相对复杂

10.2 选择链表的场景

  1. 需要频繁插入删除：文本编辑器、实时系统
  2. 内存受限环境：嵌入式系统
  3. 实现其他数据结构：栈、队列、哈希表
  4. 不确定数据规模：动态数据集合

10.3 最佳实践

  1. 合理选择链表类型：根据需求选择单向、双向或循环链表
  2. 使用哨兵节点：简化边界条件处理
  3. 注意内存管理：及时释放删除的节点
  4. 考虑缓存友好性：在性能敏感场景谨慎使用
  5. 测试边界情况：空链表、单节点、头尾操作等

10.4 扩展学习

  1. 跳表（Skip List）：多层链表，提供O(log n)的查找效率
  2. 无锁链表：并发环境下的链表实现
  3. 持久化链表：函数式编程中的不可变链表
  4. 十字链表：稀疏矩阵的存储结构

链表是数据结构学习的重要基础，深入理解链表的原理和实现，对于提高编程能力和解决复杂问题具有重要意义。希望本文能够帮助读者全面掌握链表这一重要数据结构。

# 数据结构 # 链表 # c++ # c语言 # 开发语言 # java
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

avatar 魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

avatar 魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

avatar 魔乐社区