学校-链表相关操作复习笔记

链表相关操作复习笔记

链表合并（Merge 函数）

源代码

List Merge( List L1, List L2 ){
    List p1 = L1->Next;
    List p2 = L2->Next;
    PtrToNode newNode = (PtrToNode)malloc(sizeof(struct Node));
    newNode->Next = NULL;
    List p3 = newNode;
    while (p1 != NULL && p2 != NULL){
        if (p1->Data <= p2->Data){
            p3->Next = p1;
            p3 = p3->Next;
            p1 = p1->Next;
        }
        else{
            p3->Next = p2;
            p3 = p3->Next;
            p2 = p2->Next;
        }
    }
    if (p1 == NULL){
        p3->Next = p2;
    }
    else{
        p3->Next = p1;
    }
    L1->Next = NULL;
    L2->Next = NULL;
    return newNode;
}

函数解释
功能：合并两个有序单链表（假设 L1 和 L2 均为升序），返回一个新的有序链表，且原链表 L1 和 L2 的后续节点被清空。
参数：L1和L2为待合并的有序链表（带头节点）。
实现逻辑：
定义指针p1、p2分别指向 L1、L2 的第一个数据节点；
创建新的头节点newNode作为合并后链表的头，p3为合并链表的当前尾指针；
循环比较p1和p2指向的节点值，将较小的节点链接到p3后面，并移动对应指针；
当其中一个链表遍历完毕后，将另一个链表的剩余部分链接到合并链表尾部；
清空原链表 L1 和 L2 的后续节点（L1->Next = NULL、L2->Next = NULL）；
返回合并后链表的头节点newNode。

插入元素（Insert 函数）

源代码

List Insert( List L, ElementType X ){
    PtrToNode p = (PtrToNode)malloc(sizeof(struct Node));
    p->Data = X;
    p->Next = NULL;
    List q = L;
    while(q != NULL && q->Next != NULL && q->Next->Data < X){
        q = q->Next;
    }
    p->Next = q->Next;
    q->Next = p;
    return L;
}

函数解释
功能：在有序单链表（升序）中插入元素 X，保持链表的有序性。
参数：L为有序链表（带头节点），X为待插入的元素。
实现逻辑：
创建新节点p，存储元素 X；
定义指针q从链表头节点开始遍历，找到第一个 “后续节点值大于等于 X” 的节点位置；
将新节点p插入到q和q->Next之间（修改指针：p->Next = q->Next、q->Next = p）；
返回原链表头节点 L（链表头不变）。

查找倒数第 m 个元素（Find 函数）

源代码

ElementType Find( List L, int m ){
    List p1 = L;
    List p2 = L;
    int i = 0;
    for (i = 0; i < m; i++){
        if (p1 == NULL){
            return ERROR;
        }
        p1 = p1->Next;
    }
    while(p1 != NULL){
        p1 = p1->Next;
        p2 = p2->Next;
    }
    return p2->Data;
}

函数解释
功能：查找单链表中倒数第 m 个元素的值，若不存在则返回 ERROR。
参数：L为单链表（带头节点），m为倒数位置。
实现逻辑：
使用双指针p1和p2，初始均指向头节点 L；
先让p1向前移动 m 步：若移动过程中p1为空，说明链表长度小于 m，返回 ERROR；
然后让p1和p2同时向前移动，直到p1为空；此时p2指向的节点即为倒数第 m 个节点；
返回p2节点的数据值。

单链表逆转（Reverse 函数）

源代码

List Reverse( List L ){
    if (L == NULL || L->Next == NULL){
        return L;
    }
    List prev = NULL;
    List curr = L;
    List next = NULL;
    while (curr != NULL){
        next = curr->Next;
        curr->Next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

函数解释
功能：逆转单链表（不带头节点，直接逆转数据节点）。
参数：L为待逆转的单链表（第一个节点为数据节点）。
实现逻辑：
特殊情况处理：若链表为空或只有一个节点，直接返回原链表；
定义三个指针：prev（前一个节点，初始为 NULL）、curr（当前节点，初始为 L）、next（下一个节点，临时存储）；
循环遍历链表，逐个反转节点指向：
先用next保存curr的下一个节点；
将curr的Next指向prev（反转指针）；
移动prev和curr到下一个位置（prev = curr、curr = next）；
循环结束后，prev为逆转后链表的头节点，返回prev。

求链表长度（Length 函数）

源代码

int Length( List L ){
    List p = L;
    int count = 0;
    while (p != NULL){
        p = p->Next;
        count++;
    }
    return count;
}

函数解释
功能：计算单链表的长度（节点总数）。
参数：L为单链表（第一个节点为数据节点）。
实现逻辑：
定义指针p从链表头开始遍历，count为计数变量（初始为 0）；
每遍历一个节点，count加 1，直到p为空（遍历结束）；
返回count（即链表长度）。

删除重复元素（deleteDuplicates 函数）

源代码

LinkNode* deleteDuplicates(LinkNode *L){
    if (L == NULL || L->next == NULL){
        return L;
    }
    LinkNode* p = L;
    while (p->next != NULL){
        if (p->data == p->next->data){
            p->next = p->next->next;
        }
        else{
            p = p->next;
        }
    }
    return L;
}

函数解释
功能：删除排序单链表中的重复元素（保留一个）。
参数：L为有序单链表（升序，第一个节点为数据节点）。
实现逻辑：
特殊情况处理：若链表为空或只有一个节点，直接返回原链表；
定义指针p从链表头开始遍历；
循环判断p的下一个节点是否与p的值相同：
若相同，删除下一个节点（p->next = p->next->next）；
若不同，移动p到下一个节点（p = p->next）；
返回处理后的链表头节点 L。

删除指定值元素（removeElements 函数）

源代码

struct ListNode* removeElements(struct ListNode* head, int val){
    while (head != NULL && head->val == val) {
        head = head->next;
    }
    if (head == NULL) {
        return NULL;
    }
    struct ListNode* p1 = head->next;
    struct ListNode* p2 = head;
    while(p1 != NULL){
        if (p1->val == val){
            p2->next = p2->next->next;
            p1 = p1->next;
            continue;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return head;
}

函数解释
功能：删除单链表中所有值为 val 的节点。
参数：head为单链表头节点，val为待删除的值。
实现逻辑：
先处理头节点：若头节点值为 val，直接移动头节点（head = head->next），直到头节点值不为 val 或链表为空；
若链表为空，返回 NULL；
定义双指针p1（当前节点，初始为head->next）和p2（前一个节点，初始为 head）；
遍历后续节点：若p1的值为 val，删除p1（p2->next = p2->next->next）；否则同时移动p1和p2；
返回处理后的头节点 head。

查找共享后缀（Suffix 函数）

源代码

PtrToNode Suffix( List L1, List L2 ){
    List p1 = L1;
    List p2 = L2;
    int count1 = 0;
    int count2 = 0;
    int count3;
    int i;
    while (p1 != NULL){
        count1++;
        p1 = p1->Next;
    }
    while (p2 != NULL){
        count2++;
        p2 = p2->Next;
    }
    p1 = L1;
    p2 = L2;
    if (count1 > count2){
        count3 = count1 - count2;
        for(i = 0; i < count3; i++){
            p1 = p1->Next;
        }
    }
    else{
        count3 = count2 - count1;
        for(i = 0; i < count3; i++){
            p2 = p2->Next;
        }
    }
    while(p1 != NULL){
        if (p1 == p2){
            return p1;
        }
        p1 = p1->Next;
        p2 = p2->Next;
    }
    return NULL;
}

函数解释
功能：查找两个单链表的共享后缀的起始节点（若存在）。
参数：L1和L2为两个单链表（带头节点）。
实现逻辑：
计算两个链表的长度count1（L1 长度）和count2（L2 长度）；
让较长链表的指针先移动 “长度差” 步（使两指针到链表尾的距离相同）；
同时移动两个链表的指针，直到找到第一个相同的节点（地址相同），即为共享后缀的起始节点；
若遍历结束未找到相同节点，返回 NULL。

分段逆转（K_Reverse 函数）

源代码

void K_Reverse( List L, int K ){
    if (K <= 1){
        return;
    }
    List p1 = L->Next;
    int count = 0;
    while(p1 != NULL){
        count++;
        p1 = p1->Next;
    }
    if (count < K){
        return;
    }
    p1 = L;
    int t = count/K;
    int i, j;
    for (i = 0; i < t; i++){
        List tail = p1->Next;
        List curr = p1->Next->Next;
        for (j = 0; j < K - 1; j++){
            tail->Next = curr->Next;
            curr->Next = p1->Next;
            p1->Next = curr;
            curr = tail->Next;
        }
        p1 = tail;
    }
}

函数解释
功能：将单链表按每 K 个节点为一段进行逆转（若总长度不是 K 的整数倍，最后不足 K 的部分不逆转）。
参数：L为单链表的头节点（带头节点），K为每段的节点数。
实现逻辑：
特殊情况处理：若K <= 1或链表长度小于 K，直接返回；
计算链表总长度count，确定可逆转的段数t = count / K；
逐段逆转：
每段以p1为前驱节点（初始为头节点 L）；
tail为当前段的第一个节点（逆转后成为段尾）；
curr为待逆转的节点，通过头插法将curr插入到p1之后，完成每段的逆转；
每段逆转后，p1更新为当前段的尾节点（tail），继续下一段；
无返回值，直接修改原链表。

头插法建表与打印（buildLinkedList 和 printLinkedList 函数）

源代码

struct Node* buildLinkedList(int* arr, int n){
    int i;
    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->link = NULL;
    for (i = 0; i < n; i++){
        struct Node* p = (struct Node*)malloc(sizeof(struct Node));
        p->data = arr[i];
        p->link = head->link;
        head->link = p;
    }
    return head->link;
}
void printLinkedList(struct Node* head){
    struct Node* p = head;
    int flag = 1;
    while(p != NULL){
        if (flag == 1){
            printf("%d", p->data);
            p = p->link;
            flag = 0;
        }
        else{
            printf(" %d", p->data);
            p = p->link;
        }
    }
}

函数解释
buildLinkedList 函数：
功能：使用头插法将数组元素构建为单链表。
参数：arr为存储数据的数组，n为数组长度。
实现逻辑：
创建头节点head（临时辅助节点）；
遍历数组，为每个元素创建新节点，通过头插法插入到head之后（新节点的link指向head->link，再更新head->link为新节点）；
返回真正的链表头（head->link，即第一个数据节点）。
printLinkedList 函数：
功能：打印单链表的所有元素（空格分隔，无多余空格）。
参数：head为单链表的头节点（第一个数据节点）。
实现逻辑：
定义指针p遍历链表，flag标记是否为第一个元素；
第一个元素直接打印，后续元素前加空格，避免结尾多余空格；
无返回值，直接输出结果。