链表

📙 第四部分：链表

---

第15讲：单链表 ⭐⭐

🔑 知识点讲解

链表是动态数据结构，不需要连续内存。

单链表节点：
    typedef struct Node {
        int data;           // 数据域
        struct Node *next;  // 指针域，指向下一个节点
    } Node;

头指针 vs 头节点：
    头指针：指向第一个节点的指针
    头节点：在第一个数据节点前加一个空节点（简化操作）
基本操作：
    1. 创建链表
    2. 头插法 / 尾插法
    3. 插入节点
    4. 删除节点
    5. 查找节点
    6. 链表反转 ⭐（高频考题）
    7. 求链表长度

完整单链表实现

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

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

// 创建头节点
Node* createList() {
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = 0;    // 头节点data可以存链表长度
    head->next = NULL;
    return head;
}

// 尾插法建表
void insertTail(Node *head, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = NULL;
    
    Node *p = head;
    while (p->next != NULL)
        p = p->next;
    p->next = newNode;
}

// 头插法建表（结果与输入顺序相反）
void insertHead(Node *head, int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = head->next;
    head->next = newNode;
}

// 在第pos个位置后插入
int insertAt(Node *head, int pos, int val) {
    Node *p = head;
    int i = 0;
    while (p != NULL && i < pos) {
        p = p->next;
        i++;
    }
    if (p == NULL) return 0;  // 位置无效
    
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = p->next;
    p->next = newNode;
    return 1;
}

// 删除值为val的第一个节点
int deleteNode(Node *head, int val) {
    Node *p = head;
    while (p->next != NULL) {
        if (p->next->data == val) {
            Node *temp = p->next;
            p->next = temp->next;
            free(temp);
            return 1;
        }
        p = p->next;
    }
    return 0;  // 未找到
}

// 反转【带头结点】的单链表，head 是头节点指针
void reverseList(Node *head) {
    // 定义三个辅助指针：前一个、当前、下一个
    Node *prev = NULL;   // 前驱指针，一开始指向空
    Node *curr = head->next;  // 当前指针，从【第一个有效节点】开始
    Node *next;   // 临时保存下一个节点
    
    // 遍历整个链表，直到当前节点为空（遍历结束）
    while (curr != NULL) {
        next = curr->next;    // 第一步：先保存下一个节点（不然后面找不到了）
        curr->next = prev;    // 第二步：反转！当前节点指向前一个节点
        prev = curr;          // 第三步：前驱指针向后移动
        curr = next;          // 第四步：当前指针向后移动
    }
    
    // 循环结束后，prev 就是反转后的第一个有效节点
    head->next = prev;        // 让头节点重新指向新的链表头部
}

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

// 释放链表
void freeList(Node *head) {
    Node *p = head, *temp;
    while (p != NULL) {
        temp = p;
        p = p->next;
        free(temp);
    }
}

int main() {
    Node *list = createList();
    
    // 尾插法：1 2 3 4 5
    for (int i = 1; i <= 5; i++)
        insertTail(list, i);
    
    printf("原链表: ");
    printList(list);
    
    // 反转
    reverseList(list);
    printf("反转后: ");
    printList(list);
    
    // 删除值为3的节点
    deleteNode(list, 3);
    printf("删除3: ");
    printList(list);
    
    freeList(list);
    return 0;
}

输出：

原链表: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
反转后: 5 -> 4 -> 3 -> 2 -> 1 -> NULL
删除3: 5 -> 4 -> 2 -> 1 -> NULL

✏️ 练习10：合并两个有序链表

题目：将两个升序链表合并为一个升序链表。

Node* mergeSortedLists(Node *h1, Node *h2) {
    Node *result = createList();
    Node *p1 = h1->next, *p2 = h2->next;
    Node *tail = result;
    
    while (p1 != NULL && p2 != NULL) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        if (p1->data <= p2->data) {
            newNode->data = p1->data;
            p1 = p1->next;
        } else {
            newNode->data = p2->data;
            p2 = p2->next;
        }
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    
    // 处理剩余节点
    Node *remaining = (p1 != NULL) ? p1 : p2;
    while (remaining != NULL) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = remaining->data;
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
        remaining = remaining->next;
    }
    
    return result;
}

---

第16讲：双链表

🔑 知识点讲解

双链表每个节点有两个指针：前驱和后继。

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

优点：可以双向遍历，删除给定节点时间O(1)（单链表需要知道前驱）
缺点：额外的空间开销

插入操作（在 p 节点后插入 s）：
    s->next = p->next;
    s->prev = p;
    if (p->next) p->next->prev = s;
    p->next = s;

删除操作（删除 p 节点）：
    p->prev->next = p->next;
    if (p->next) p->next->prev = p->prev;
    free(p);

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

typedef struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode* createDList() {
    DNode *head = (DNode *)malloc(sizeof(DNode));
    head->data = 0;
    head->prev = NULL;
    head->next = NULL;
    return head;
}

void insertTailD(DNode *head, int val) {
    DNode *newNode = (DNode *)malloc(sizeof(DNode));
    newNode->data = val;
    newNode->next = NULL;
    
    DNode *p = head;
    while (p->next) p = p->next;
    
    newNode->prev = p;
    p->next = newNode;
}

void printDList(DNode *head) {
    DNode *p = head->next;
    printf("正向: ");
    DNode *tail = NULL;
    while (p) {
        printf("%d <-> ", p->data);
        tail = p;
        p = p->next;
    }
    printf("NULL\n");
    
    printf("反向: ");
    while (tail && tail != head) {
        printf("%d <-> ", tail->data);
        tail = tail->prev;
    }
    printf("HEAD\n");
}

int main() {
    DNode *list = createDList();
    for (int i = 1; i <= 5; i++)
        insertTailD(list, i);
    printDList(list);
    return 0;
}