• 【数据结构-链表】链表的相关算法

    文章目录


    （只是写了个大致思路，不具备可执行性）

    1 删除元素

    1.1 删除值为 x 的所有结点

    1.1.1 不带头结点的单链表
    • 正常写法：
    void Delete_X (LinkList &L, int x){
    LinkNode *p = L;
    LinkNode *prevNode; // 记录 p 的前驱结点
    LinkNode *nextNode; // 记录 p 的后继结点
    
    while (p != NULL){
        if (p->data == x){
            if (p == L){ // 如果是头结点
                nextNode = p->next;
                free(p);
                L = nextNode;
            }
            else{ // 如果是中间结点或尾结点
                nextNode = p->next;
                free(p);
                prevNode->next = nextNode;
            }
        }
        prevNode = p; // 记录 p 的前驱结点
        p = p->next;  // 遍历下一个结点 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 递归写法：
    void Delete_X (LinkList &L, int x){
    LinkNode *p;
    
    if (L->data == x){
        p = L;
        L = L->next;
        free(p);
        Delete_X(L, x);
    }
    else
        Delete_X(L->next, x);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    1.1.2 带头结点的单链表
    void Delete_X (LinkList &L, int x){
    LinkNode *p;
    LinkNode *prevNode; // 记录 p 的前驱结点
    LinkNode *nextNode; // 记录 p 的后继结点
    
    p = L->next;
    prevNode = L;
    while (p != NULL){
        if (p->data == x){ 
            nextNode = p->next;
            free(p);
            prevNode->next = nextNode;
        }
        prevNode = p; // 记录 p 的前驱结点
        p = p->next;  // 遍历下一个结点 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    【注】欲删除值介于 s 和 t 之间的所有结点，需把条件改为(s <= p->data) && (p->data <= t)。

    1.2 删除重复元素

    1.2.1 不带头结点的单链有序表
    void Delete_Same (LinkList &L){
    LinkNode *p = L; // 初始指向链表头部
    LinkNode *nextNode; // 记录 p 的后继结点
    
    while (p != NULL){
        nextNode = p->next; // 记录 p 的后继结点
        if ((nextNode != NULL) && (nextNode->data == p->data)){ // 发现重复元素
            p->next = nextNode->next;
            free(nextNode);
        }
        else // 没有发现重复元素
            p = p->next;  // 遍历下一个结点 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    1.2.2 带头结点的单链有序表
    void Delete_Same (LinkList &L){
    LinkNode *p = L->next; // 初始指向链表第一个结点
    LinkNode *nextNode; // 记录 p 的后继结点
    
    while (p != NULL){
        nextNode = p->next; // 记录 p 的后继结点
        if ((nextNode != NULL) && (nextNode->data == p->data)){ // 发现重复元素
            p->next = nextNode->next;
            free(nextNode);
        }
        else // 没有发现重复元素
            p = p->next;  // 遍历下一个结点 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    2 链表逆置

    2.1 逆序输出结点

    2.1.1 不带头结点的单链表

    设 L 为不带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

    void Reverse_Print (LinkList &L){
    LinkNode *p = L; // 指向链表头部
    Stack S; // 定义栈
    int x;
    
    InitStack(S); // 初始化栈
    
    while (p != NULL){
        PushStack(S, p->data); // 入栈
        p = p->next;
    }
    
    while (!EmptyStack(S)){
        x = PopStack(S); // 出栈
        输出 x;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    2.1.2 带头结点的单链表

    设 L 为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。

    void Reverse_Print (LinkList &L){
    LinkNode *p = L->next;
    Stack S; // 定义栈
    int x;
    
    InitStack(S); // 初始化栈
    
    while (p != NULL){
        PushStack(S, p->data); // 入栈
        p = p->next;
    }
    
    while (!EmptyStack(S)){
        x = PopStack(S); // 出栈
        输出 x;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    2.2 就地逆置

    2.2.1 不带头结点的单链表

    试编写一个算法将不带头结点的单链表就地逆置。

    就地：空间复杂度为 O(1)。

    思路：总是把第一个结点取下来，然后用尾插法重新建立链表。

    LinkList Reverse (LinkList &L){
    LinkNode *head = L;         // 指向原链表头部
    LinkNode *nextNode;         // 保存原链表头部的指针域
    LinkNode *newHead = NULL;   // 指向新链表头部
    
    while (head != NULL){
        nextNode = head->next;  // 保存原链表头部的指针域
        head->next = newHead;   // 原链表头部的指针域指向新链表头部
        newHead = head;         // 新链表头部更新
        head = nextNode;        // 原链表头部更新
    }
    
    L = newHead;
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    2.2.2 带头结点的单链表
    LinkList Reverse (LinkList &L){
    LinkNode *head = L->next;   // 指向原链表第一个结点
    LinkNode *nextNode;         // 保存原链表头部的指针域
    LinkNode *newHead = NULL;   // 指向新链表头部
    
    while (head != NULL){
        nextNode = head->next;  // 保存原链表头部的指针域
        head->next = newHead;   // 原链表头部的指针域指向新链表头部
        newHead = head;         // 新链表头指针更新
        head = nextNode;        // 原链表头指针更新
    }
    
    L->next = newHead;          // 更新头结点指针域，头结点插到新链表头部
    return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    3 链表有序

    3.1 链表排序

    3.1.1 不带头结点的单链表

    有一个不带头结点的单链表 L，设计一个算法使其元素递增有序。

    思路：每次取出原链表的第一个元素，与有序链表中每个元素进行对比，然后插入到有序链表的相应位置。

    void Sort (LinkList &L){
    LinkNode *head = L;             // 原链表头指针
    LinkNode *nextNode;             // 保存原链表头部的指针域
    LinkNode *newHead;              // 有序链表头指针
    LinkNode *newNode, *newPrev;    // 有序链表结点指针及其前驱结点
    
    newHead = (LinkNode *) malloc(sizeof(LinkNode));
    newHead->data = L->data;
    newHead->next = NULL;
    
    while (head != NULL){
        newPrev = NULL;
        newNode = newHead;
        
        while ((newNode != NULL) && (head->data <= newNode->data)){ // 有序链表指针指向第一个大于 head 元素的结点
            newPrev = newNode;       // 记录其前驱结点
            newNode = newNode->next; // 继续遍历新链表
        }                            // 运行到此处，newPrev 在前，newNode 在后
        
        nextNode = head->next;  // 保存原链表头部的指针域
        if (newPrev == NULL){   // 如果要插入有序链表的头部位置
            head->next = newNode; 
            newHead = head;     // 更新有序链表头指针
        }
        else{                   // 如果要插入有序链表的中间和尾部位置
            newPrev->next = head;
            head->next = newNode;
        }
        head = nextNode;        // 继续遍历原链表
    }
    L = newHead;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    3.1.2 带头结点的单链表

    有一个带头结点的单链表 L，设计一个算法使其元素递增有序。

    void Sort (LinkList &L){
    LinkNode *head = L->next;       // 原链表头指针
    LinkNode *nextNode;             // 保存原链表头部的指针域
    LinkNode *newNode, *newPrev;    // 有序链表结点指针及其前驱结点
    
    while (head != NULL){
        newPrev = L;                // 原链表头结点作为新链表的头结点
        newNode = L->next;
        
        while ((newNode != NULL) && (head->data <= newNode->data)){ // 有序链表指针指向第一个大于 head 元素的结点
            newPrev = newNode;       // 记录其前驱结点
            newNode = newNode->next; // 继续遍历新链表
        }                            // 运行到此处，newPrev 在前，newNode 在后
        
        nextNode = head->next;  // 保存原链表头部的指针域
        newPrev->next = head;
        head->next = newNode;
        head = nextNode;        // 继续遍历原链表
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    3.2 链表有序输出

    3.2.1 不带头结点的单链表

    按递增次序输出单链表各结点的数据元素，每输出一个将该结点删除。

    思路：每次遍历链表找出最小元素，输出该元素，然后删除。

    void Print_Min (LinkList &L){
    LinkNode *prev; // 扫描指针
    LinkNode *prevNode, *nodeMin = L, *nextNode;  // 最小值结点（初始指向链表第一个结点）以及其前驱和后继结点
    int min = L->data;
    
    while (L != NULL){
        prev = L;
        while (prev->next != NULL){
            if (prev->next->data < min){
                prevNode = prev;            // 记录最小值的前驱结点
                nodeMin = prev->next;       // 记录最小值结点
                min = nodeMin->data;  
                nextNode = prev->next->next;// 记录最小值的后继结点
            }
            prev = prev->next;
        }
        输出 min;
        
        if (nodeMin == L){ // 如果第一个结点为最小值
            free(nodeMin);
            L = nextNode;
        }
        else{
            free(nodeMin);
            prevNode->next = nextNode;
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    3.2.2 带头结点的单链表

    按递增次序输出单链表各结点的数据元素，每输出一个将该结点删除。

    思路：每次遍历链表找出最小元素，输出该元素，然后删除。

    void Print_Min (LinkList &L){
    LinkNode *prev; // 扫描指针
    LinkNode *nodeMin = L->next, *prevNode, *nextNode;  // 最小值结点（初始指向链表第一个结点）以及其前驱和后继结点
    int min = L->next->data;
    
    while (L->next != NULL){ // 循环到只剩头结点
        prev = L;
        while (prev->next != NULL){
            if (prev->next->data < min){
                prevNode = prev;            // 记录最小值的前驱结点
                nodeMin = prev->next;       // 记录最小值结点
                min = nodeMin->data;
                nextNode = prev->next->next;// 记录最小值的后继结点
            }
            prev = prev->next;
        }
        
        输出 min;
        free(nodeMin); // 删除最小值结点
        prevNode->next = nextNode; 
    }
    
    free(L);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    4 合并链表

    4.1 两个递增链表合并为一个递增链表

    4.1.1 不带头结点的单链表

    思路：设置双指针，建立新链表，运用尾插法，把两个链表的结点按升序插入即可。

    LinkList Merge (LinkList &A, LinkList &B){
    LinkNode *pa = A, *pb = B; // 扫描指针，指向前驱结点
    LinkNode *prevNode, *node, *nextNode; // 记录前驱结点、当前要插入的结点、后继结点
    LinkNode *C, *newNode;    // 新链表
    LinkNode *tail; // 新链表的尾指针
    
    if (A->data < B->data){ // 单独处理两个链表的第一个结点，这两个结点单独保留，将问题转化为“带头结点的单链表”
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第一个结点
        newNode->data = A->data;
        C = newNode;
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第二个结点
        newNode->data = B->data;
        newNode->next = NULL;
        C->next = newNode;
        tail = newNode;
    }
    else{
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第一个结点
        newNode->data = B->data;
        C = newNode;
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第二个结点
        newNode->data = A->data;
        newNode->next = NULL;
        C->next = newNode;
        tail = newNode;
    }

    while ((pa->next != NULL) && (pb->next != NULL)){
        if (pb->next->data < pa->next->data){
            prevNode = pb;          // 记录前驱结点···（1）
            node = pb->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode; // 前驱结点指向后继结点···（2）
            tail->next = node;      // 往新链表尾插当前结点···（3）
            tail = node;            // 更新新链表尾指针
            pb = pb->next;          // 链表 B 的扫描指针继续遍历···（4）
        }
        else{
            prevNode = pa;          // 记录前驱结点···（1）
            node = pa->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode;  // 前驱结点指向后继结点···（2）
            tail->next = node;      // 往新链表尾插当前结点···（3）
            tail = node;            // 更新新链表尾指针
            pa = pa->next;          // 链表 A 的扫描指针继续遍历···（4）
        }
    }
    
    // 运行到此处，一定有且仅有一个链表非空
    if (A->next != NULL)    // 若链表 A 还未空
        tail->next = A->next; // 新链表尾部直接插入链表 A 的剩余部分
    if (B->next != NULL)    // 若链表 B 还未空
        tail->next = B->next; // 新链表尾部直接插入链表 B 的剩余部分
        
    free(A); // 删除链表 A
    free(B); // 删除链表 B
    return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    4.1.2 带头结点的单链表

    思路：设置双指针，建立新链表，运用尾插法，把两个链表的结点按升序插入即可。

    LinkList Merge (LinkList &A, LinkList &B){
    LinkNode *pa = A, *pb = B; // 扫描指针，指向前驱结点
    LinkNode *prevNode, *node, *nextNode; // 记录前驱结点、当前要插入的结点、后继结点
    LinkNode *C = (LinkNode *) malloc(sizeof(LinkNode)); // 新链表的头结点
    LinkNode *tail = C; // 新链表的尾指针

    while ((pa->next != NULL) && (pb->next != NULL)){
        if (pb->next->data < pa->next->data){
            prevNode = pb;          // 记录前驱结点···（1）
            node = pb->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode; // 前驱结点指向后继结点···（2）
            tail->next = node;      // 往新链表尾插当前结点···（3）
            tail = node;            // 更新新链表尾指针
            pb = pb->next;          // 链表 B 的扫描指针继续遍历···（4）
        }
        else{
            prevNode = pa;          // 记录前驱结点···（1）
            node = pa->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode;  // 前驱结点指向后继结点···（2）
            tail->next = node;      // 往新链表尾插当前结点···（3）
            tail = node;            // 更新新链表尾指针
            pa = pa->next;          // 链表 A 的扫描指针继续遍历···（4）
        }
    }
    
    // 运行到此处，一定有且仅有一个链表非空
    if (A->next != NULL)    // 若链表 A 还未空
        tail->next = A->next; // 新链表尾部直接插入链表 A 的剩余部分
    if (B->next != NULL)    // 若链表 B 还未空
        tail->next = B->next; // 新链表尾部直接插入链表 B 的剩余部分
        
    free(A); // 删除链表 A 的头结点
    free(B); // 删除链表 B 的头结点
    return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    4.2 两个递增链表合并为一个递减链表

    4.2.1 不带头结点的单链表

    思路：设置双指针，建立新链表，运用头插法，把两个链表的结点按升序插入即可。

    LinkList Merge (LinkList &A, LinkList &B){
    LinkNode *pa = A, *pb = B; // 扫描指针，指向前驱结点
    LinkNode *prevNode, *node, *nextNode; // 记录前驱结点、当前要插入的结点、后继结点
    LinkNode *C, *newNode;  // 新链表
    LinkNode *headNext;     // 新链表的头结点后继指针
    
    if (A->data > B->data){ // 单独处理两个链表的第一个结点，这两个结点单独保留，将问题转化为“带头结点的单链表”
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第一个结点
        newNode->data = A->data;
        C = newNode;
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第二个结点
        newNode->data = B->data;
        newNode->next = NULL;
        C->next = newNode;
    }
    else{
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第一个结点
        newNode->data = B->data;
        C = newNode;
        newNode = (LinkNode *) malloc(sizeof(LinkNode)); // 链表 C 的第二个结点
        newNode->data = A->data;
        newNode->next = NULL;
        C->next = newNode;
    }

    while ((pa->next != NULL) && (pb->next != NULL)){
        if (pb->next->data < pa->next->data){
            prevNode = pb;          // 记录前驱结点···（1）
            node = pb->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode; // 前驱结点指向后继结点···（2）
            node->next = C;         // 当前结点插入到新链表中···（3）
            C = node;               // 更新新链表的头指针
            pb = pb->next;          // 链表 B 的扫描指针继续遍历···（4）
        }
        else{
            prevNode = pa;          // 记录前驱结点···（1）
            node = pa->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode;  // 前驱结点指向后继结点···（2）
            node->next = C;         // 当前结点插入到新链表中···（3）
            C = node;               // 更新新链表的头指针
            pa = pa->next;          // 链表 A 的扫描指针继续遍历···（4）
        }
    }
    
    // 运行到此处，一定有且仅有一个链表非空
    if (A->next != NULL){       // 若链表 A 还未空
        while (pa->next != NULL)// 先找到链表 A 的尾部
            pa = pa->next;
        headNext = head->next;  // 记录新链表头结点的后继指针
        head->next = A->next;   // 新链表尾部直接插入链表 A 的剩余部分
        pa->next = headNext;
    }
    if (B->next != NULL){       // 若链表 B 还未空
        while (pb->next != NULL)// 先找到链表 B 的尾部
            pb = pb->next;
        headNext = head->next;  // 记录新链表头结点的后继指针
        tail->next = B->next;   // 新链表尾部直接插入链表 B 的剩余部分
        pb->next = headNext;
    }
        
    free(A); // 删除链表 A
    free(B); // 删除链表 B
    return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    4.2.2 带头结点的单链表

    思路：设置双指针，建立新链表，运用头插法，把两个链表的结点按升序插入即可。

    LinkList Merge (LinkList &A, LinkList &B){
    LinkNode *pa = A, *pb = B; // 扫描指针，指向前驱结点
    LinkNode *prevNode, *node, *nextNode; // 记录前驱结点、当前要插入的结点、后继结点
    LinkNode *C = (LinkNode *) malloc(sizeof(LinkNode)); // 新链表的头结点
    LinkNode *head = C, *headNext = C->next; // 新链表的头结点，及头结点的后继指针

    while ((pa->next != NULL) && (pb->next != NULL)){
        if (pb->next->data < pa->next->data){
            prevNode = pb;          // 记录前驱结点···（1）
            node = pb->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode; // 前驱结点指向后继结点···（2）
            headNext = head->next;  // 记录新链表头结点的后继指针···（3）
            head->next = node;      // 往新链表尾插当前结点
            node->next = headNext;  // 当前结点指向头结点的后继指针
            pb = pb->next;          // 链表 B 的扫描指针继续遍历···（4）
        }
        else{
            prevNode = pa;          // 记录前驱结点···（1）
            node = pa->next;        // 记录当前要插入的结点
            nextNode = node->next;  // 记录后继结点
            prevNode->next = nextNode;  // 前驱结点指向后继结点···（2）
            headNext = head->next;  // 记录新链表头结点的后继指针···（3）
            head->next = node;      // 往新链表尾插当前结点
            node->next = headNext;  // 当前结点指向头结点的后继指针
            pa = pa->next;          // 链表 A 的扫描指针继续遍历···（4）
        }
    }
    
    // 运行到此处，一定有且仅有一个链表非空
    if (A->next != NULL){       // 若链表 A 还未空
        while (pa->next != NULL)// 先找到链表 A 的尾部
            pa = pa->next;
        headNext = head->next;  // 记录新链表头结点的后继指针
        head->next = A->next;   // 新链表尾部直接插入链表 A 的剩余部分
        pa->next = headNext;
    }
    if (B->next != NULL){       // 若链表 B 还未空
        while (pb->next != NULL)// 先找到链表 B 的尾部
            pb = pb->next;
        headNext = head->next;  // 记录新链表头结点的后继指针
        tail->next = B->next;   // 新链表尾部直接插入链表 B 的剩余部分
        pb->next = headNext;
    }
        
    free(A); // 删除链表 A 的头结点
    free(B); // 删除链表 B 的头结点
    return C;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    5 拆分链表

    5.1 不带头结点的单链表

    设 C = {a1, b1, a2, b2, a3, b3,···}为线性表，采用不带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A = {a1, a2, ···, an}, B = {bn,···,b2, b1}。

    思路：链表 A 使用尾插法，链表 B 使用头插法。

    void Split (LinkList &C){
    LinkNode *headC, *headNextC, *headNextNextC; // headC 指向链表 C 的第二个元素，将其当做头结点
    LinkNode *tailA, *headB; // 链表 A 的尾指针，链表 B 的头指针
    LinkNode *A, *B;
    bool flag = true;
    
    // 首先单独处理链表 C 的第一个和第二个元素，将问题转化为“带头结点的单链表”
    A = (LinkNode *) malloc(sizeof(LinkNode));
    B = (LinkNode *) malloc(sizeof(LinkNode));
    A->data = C->data;
    A->next = NULL;
    B->data = C->next->data;
    B->next = NULL;
    tailA = A;
    headB = B;
    
    headC = C->next->next; // headC 指向第二个元素，将其当做头结点
    while (headC->next != NULL){
        headNextC = headC->next;         // 链表 C 的第三个元素
        headNextNextC = headNextC->next; // 链表 C 的第四个元素
        headC->next = headNextNextC;     // 将链表 C 的第三个元素脱离出来
        
        if (flag == true){      // 轮到 an
            tailA->next = headNextC;    // 尾插入到链表 A
            tailA = headNextC;
            flag = false;
        }
        else{                   // 轮到 bn
            headNextC->next = headB;    // 头插入到链表 B
            headB = headNextC;
            flag = true;
        }
    }
    
    free(C->next);
    free(C);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    5.2 带头结点的单链表

    设 C= {a1, b1, a2, b2, a3, b3,···} 为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A = {a1, a2, ···, an}, B = {bn,···,b2, b1}。

    思路：链表 A 使用尾插法，链表 B 使用头插法。

    void Split (LinkList &C){
    LinkNode *headC, *headNextC; // 链表 C 的第一个元素及其后继结点，链表 C 的第一个元素也是待插入元素
    LinkNode *tailA, *headB, *headNextB; // 链表 A 的尾指针，链表 B 的第一个元素及其后继结点
    LinkNode *A, *B;
    bool flag = true;
    
    A = (LinkNode *) malloc(sizeof(LinkNode));
    B = (LinkNode *) malloc(sizeof(LinkNode));
    A->next = NULL;
    B->next = NULL;
    tailA = A;
    headB = B;
    
    while (C->next != NULL){
        headC = C->next;        // 链表 C 的第一个元素
        headNextC = headC->next; // 链表 C 的第二个元素
        C->next = headNextC;    // 将链表 C 的第一个元素脱离出来
        
        if (flag == true){      // 轮到 an
            tailA->next = headC;        // 尾插入到链表 A
            tailA = headC;
            flag = false;
        }
        else{                   // 轮到 bn
            headB = B->next;            // 链表 B 的第一个元素
            headNextB = headB->next;    // 链表 B 的第二个元素
            B->next = headC;            // 头插入到链表 B
            headC->next = headNextB;
            flag = true;
        }
    }
    
    free(C);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    6 链表对称和链表环

    6.1 判断链表对称

    设计一个算法用于判断带头结点的循环双链表是否对称。

    bool Test (LinkList &L){
    LinkNode *p, *q;
    
    p = L->next;
    q = L->prev;
    
    // p != q 为奇数个结点的情况，检测结束时两指针会出现相遇
    // q != p->next 为偶数个结点的情况，检测结束时两指针相邻
    while ((p != q) && (q != p->next)){
        if (p->data != q->data)
            return false;
        else{
            p = p->next;
            q = q->prev;
        }
    }
    
    return true;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    6.2 判断链表是否有环

    单链表有环，是指单链表中某个节点的 next 指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。

    条件：带头结点的单链表。

    • 判断是否有环：通常使用快慢指针的方法，也就是说一个每次指针走两步，一个指针每次只走一步，如果链表有环，则两个指针总会在一个节点上相遇，若无环，则不会相遇。
    bool Ring (LinkNode &L){
    LinkNode *slow, *fast;
    
    slow = L->next;
    fast = L->next;
    
    while ((fast != NULL) &&  (fast->next != NULL)){
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
            return true;
    }
    
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 返回环的开始结点：已知单链表有环的情况下，找到环开始的位置。当快慢指针相遇时，让其中一个指针指向头结点，然后让两个节点以相同的速度前进，再次相遇时所在的节点位置就是环开始的位置。
    LNode *Ring (LinkNode &L){
    LinkNode *slow, *fast;
    
    slow = L->next;
    fast = L->next;
    
    while ((fast != NULL) &&  (fast->next != NULL) && (slow != fast)){
        slow = slow->next;
        fast = fast->next->next;
    }
    
    if ((slow == NULL) || (fast->next == NULL))
        return NULL;
    
    fast = L->next;
    
    while (fast != slow){
        fast = fast->next;
        slow = slow->next;
    }
    return fast;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    7 求两个链表的公共结点

    给定两个带头结点的单链表，编写算法找出两个链表的公共结点。

    算法思路如下：

    • 先求出两个链表的长度之差 d；
    • 在较长的链表上先遍历 d 个结点；
    • 再同步遍历两个链表，直到找到相同的结点。
    LinkNode *Find_Common (LinkList L1, LinkList L2){
    LinkNode *p1 = L1;
    LinkNode *p2 = L2;
    int len1 = 0, len2 = 0;
    
    // 分别求出两个链表的长度
    while (p1->next != NULL){
        p1 = p1->next;
        len1++;
    }
    while (p2->next != NULL){
        p2 = p2->next;
        len2++;
    }
    
    // 求出两个链表的长度之差 d
    LinkNode long, short;
    int d = 0;
    
    if (len1 > len2){
        long = L1->next;
        short = L2->next;
        d = len1 - len2;
    }
    else{
        long = L2->next;
        short = L1->next;
        d = len2 - len1;
    }
    
    // 在较长的链表上先遍历 d 个结点
    while (d != 0){
        d--;
        long = long->next;
    }
    
    // 再同步遍历两个链表，直到找到相同的结点
    while (long != NULL){
        if (long == short)
            return long;
        else{
            long = long->next;
            short = short->next;
        }
    }
    return NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
  • 相关阅读:
    高级测试开发进阶知识详解
    LeetCode 779. 第K个语法符号
    Java随笔-泛型
    基于FPGA的图像二值化处理,包括tb测试文件和MATLAB辅助验证
    SpringMVC源码分析（一）启动流程分析
    Hadoop3：MapReduce中的Partition原理及自定义Partition
    树莓派底层开发-----交叉编译
    【python绘图—colorbar操作学习】
    Oracle-性能优化篇-分区表
    一起来领略JDK8中的流式编程的魅力
  • 原文地址：https://blog.csdn.net/baidu_39514357/article/details/127733957