链表
数据结构
|
|
|
154

1899 字
|
45 分钟

文章目录[隐藏]

链表

1. 定义

typedef int ElemType;

// 定义链表节点结构
typedef struct LinkNode {
    ElemType data;           // 数据域
    struct LinkNode *next;   // 指针域，指向下一个节点
} LinkNode, *LinkList;

2. 初始化

bool InitLinkList(LinkList &L) {
    // 1. 分配头节点内存
    L = (LinkNode *) malloc(sizeof(LinkNode));

    // 2. 判断内存分配是否成功
    if (L == NULL) {
        return false;
    }

    // 3. 头节点指针域初始化为空
    L->next = NULL;

    return true;
}

3. 打印链表

void PrintLinkList(LinkList L) {
    // 1. 初始化指针，跳过头节点
    LinkNode *pNode = L->next; 
    printf("链表内容：");

    // 2. 遍历链表，打印每个节点的数据
    while (pNode != NULL) {
        printf("%d", pNode->data);
        pNode = pNode->next;
        if (pNode != NULL) {
            printf(" -> ");
        }
    }

    printf("\n");
}

4. 获取链表长度

int GetLinkListLength(LinkList L) {
    // 1. 初始化指针，跳过头节点
    LinkNode *pNode = L->next;
    int length = 0;

    // 2. 遍历链表，计算长度
    while (pNode != NULL) {
        length++;
        pNode = pNode->next;
    }

    // 3. 返回链表长度
    return length; 
}

5. 按序号查找链表元素

LinkNode *FindByOrder(LinkList L, int i) {
    // 1. 初始化指针，指向第一个数据节点
    LinkNode *pNode = L->next; 
    int count = 1; // 从1开始计数

    // 2. 遍历链表，找到第i个节点
    while (pNode != NULL && count < i) {
        pNode = pNode->next;
        count++;
    }

    // 3. 返回第i个节点的指针（如果存在）
    return pNode;
}

6. 按值查找链表元素

LinkNode *FindByValue(LinkList L, ElemType e) {
    // 1. 初始化指针，指向第一个数据节点
    LinkNode *pNode = L->next;

    // 2. 遍历链表，查找值为e的节点
    while (pNode != NULL && pNode->data != e) {
        pNode = pNode->next;
    }

    // 3. 返回值为e的节点的指针（如果存在）
    return pNode;
}

7. 在链表第 i 个位置插入元素 e

bool LinkNodeInsert(LinkList &L, int i, ElemType e) {
    // 1. 初始化指针，指向头节点
    LinkNode *pNode = L;
    int count = 0; // 从0开始计数，插入在第i个位置

    // 2. 遍历链表，找到第i-1个节点
    while (pNode != NULL && count < i - 1) {
        pNode = pNode->next;
        count++;
    }

    // 3. 如果链表长度小于i-1，则插入失败
    if (pNode == NULL) {
        return false;
    }

    // 4. 分配新节点内存
    LinkNode *node = (LinkNode *) malloc(sizeof(LinkNode));
    // 5. 判断内存分配是否成功
    if (node == NULL) {
        return false;
    }
    // 6. 设置新节点数据
    node->data = e;
    // 7. 新节点的指针域指向第i个节点
    node->next = pNode->next;
    // 8. 第i-1个节点的指针域指向新节点
    pNode->next = node;

    return true; // 插入成功
}

8. 头插法创建链表

void CreateLinkListByHeadInsert(LinkList &L, ElemType elems[], int n) {
    // 1. 初始化链表
    InitLinkList(L);

    // 2. 循环插入元素
    for (int i = 0; i < n; i++) {
        // 3. 分配新节点内存
        LinkNode *node = (LinkNode *) malloc(sizeof(LinkNode));

        // 4. 判断内存分配是否成功
        if (node == NULL) {
            printf("内存分配失败。\n");
            return;
        }

        // 5. 设置新节点数据
        node->data = elems[i];
        // 6. 新节点的指针域指向当前链表的第一个节点
        node->next = L->next;
        // 7. 头节点的指针域指向新节点
        L->next = node;
    }
}

9. 尾插法创建链表

void CreateLinkListByTailInsert(LinkList &L, ElemType elems[], int n) {
    // 1. 初始化链表
    InitLinkList(L);

    // 2. 初始化指针，指向头节点
    LinkNode *tail = L;

    // 3. 循环插入元素
    for (int i = 0; i < n; i++) {
        // 4. 分配新节点内存
        LinkNode *node = (LinkNode *) malloc(sizeof(LinkNode));

        // 5. 判断内存分配是否成功
        if (node == NULL) {
            printf("内存分配失败。\n");
            return;
        }

        // 6. 设置新节点数据
        node->data = elems[i];
        // 7. 新节点的指针域初始化为空
        node->next = NULL;
        // 8. 尾节点的指针域指向新节点
        tail->next = node;
        // 9. 更新尾节点为新节点
        tail = node;
    }
}

10. 查找带头单链表倒数第m个位置的结点并输出该结点的值

LinkNode *FindNodeFromEnd(LinkList L, int m) {
    // 定义快慢指针，初始时都指向头节点
    LinkNode *slow = L;
    LinkNode *fast = L;

    // 快指针先走 m 步
    while (m > 0 && fast != NULL) {
        fast = fast->next;
        m--;
    }

    // 如果 m 大于链表长度，返回 NULL
    if (m > 0) {
        return NULL;
    }

    // 快慢指针同时移动，直到快指针到达链表末尾
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    // 此时慢指针指向的就是倒数第 m 个节点
    return slow;
}

image-20240728180535562

11. 已知指针 La 和 Lb 分别指向两个无头结点的单链表。编写函数完成从 La 中删除第 j 个元素开始的共 len 个元素，并将这 len 个元素插入到表 Lb 中第 j 个元素之前

// 1. 查找链表中第 j 个节点的前一个节点
LinkNode *FindPrevNode(LinkList L, int j) {
    if (j <= 0 || L == NULL) {
        return NULL;
    }
    LinkNode *prev = L;

    while(j > 1 && prev != NULL){
        prev = prev->next;
        j--;
    }

    return prev;
}

// 2. 从链表中删除第 j 个节点开始的 len 个节点
LinkNode *RemoveSubList(LinkList &L, int j, int len) {
    LinkNode *prev = FindPrevNode(L, j);

    // 检查 prev 和 prev->next 是否为空
    if (prev == NULL || prev->next == NULL) {
        return NULL;
    }

    LinkNode *start = prev->next;
    LinkNode *cur = prev;

    while(len > 0 && cur != NULL){
        cur = cur->next;
        len--;
    }

    prev->next = cur->next;
    cur->next = NULL;

    return start;
}

// 3. 从 La 中删除第 j 个元素开始的 len 个元素，并插入到 Lb 中第 j 个元素之前
void MoveSubList(LinkList &La, LinkList &Lb, int j, int len) {
    if (j <= 0 || len <= 0 || La == NULL) {
        printf("输入无效\n");
        return;
    }

    // 从 La 中删除第 j 个元素开始的 len 个元素
    LinkNode *subList = RemoveSubList(La, j, len);
    if (subList == NULL) {
        printf("La 长度小于 %d 或者 len 无效\n", j);
        return;
    }

    // 将删除的子链表插入到 Lb 中第 j 个元素之前
    LinkNode *prev = FindPrevNode(Lb, j);
    LinkNode *cur = subList;

    while(cur-> next != NULL){
        cur = cur->next;
    }

    cur->next = prev->next;
    prev->next = subList;
}

image-20240728175806187

12. 设单链表表头指针为 L,结点数据域为字符。设计时间复杂度最低的算法判断前 n/2 个字符是否与后 n/2 字符依次相同

bool IsSymmetrical(LinkList L){
    int length = GetLinkListLength(L);
    int half = length / 2;
    LinkNode *p1 = L->next;
    LinkNode *p2 = L->next;

    // p2指向链表的中间位置
    for (int i = 0; i < half; i++) {
        p2 = p2->next;
    }

    // 如果是奇数长度，跳过中间的一个元素
    if (length % 2 != 0) {
        p2 = p2->next;
    }

    // 比较前半部分和后半部分
    for (int i = 0; i < half; i++) {
        if (p1->data != p2->data) {
            return false;
        }
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}

image-20240728180039026

13. 从非递减有序的单链表中删除值相同的元素

void RemoveDuplicates(LinkList L) {
    LinkNode *cur = L->next;

    while (cur->next != NULL) {
        if (cur->data == cur->next->data) {
            LinkNode *temp = cur->next;
            cur->next = temp->next;
            free(temp);
        } else {
            cur = cur->next;
        }
    }
}

image-20240728180402118

14. 设有一个非递减的正整数单链表（有重复数），设计算法确定比 x 小的结点数量

int CountUniqueNodesLessThanX(LinkList L, ElemType x) {
    int count = 0;
    LinkNode *pNode = L->next; // 跳过头节点
    ElemType lastCounted = -1; // 记录上一个计数的值，初始化为一个不可能的值

    while (pNode != NULL) {
        if (pNode->data < x && pNode->data != lastCounted) {
            count++;
            lastCounted = pNode->data;
        }
        pNode = pNode->next;
    }

    return count;
}

image-20240728180340963

15. 删除非递减单链表 La 中与非递减表 Lb 中相同的元素

void DeleteCommonElements(LinkList &La, LinkList Lb) {
    LinkNode *preA = La;
    LinkNode *curA = La->next;
    LinkNode *curB = Lb->next;

    while(curA != NULL && curB != NULL){
        if(curA->data < curB->data){
            preA = curA;
            curA = curA->next;
        } else if(curA->data > curB->data){
            curB = curB->next;
        } else{
            preA->next = curA->next;
            free(curA);
            curA = preA->next;
        }
    }
}

image-20240728180809794

16. 已知 La,Lb,LC 是三个链表，且它们已经初始化，其元素按递增顺序排序，每个表中均无重复数据。设计算法在表 Lc 中删除同时出现在 La 和 Lb 中的所有元素

// 1. 判断元素是否在链表中
bool IsElementInLinkList(LinkList L, ElemType e) {
    LinkNode *cur = L->next;

    while(cur != NULL){
        if(cur->data == e){
            return true;
        }
        cur = cur->next;
    }

    return false;
}

// 2. 删除链表 Lc 中同时出现在链表 La 和 Lb 中的元素
void DeleteCommonElements(LinkList &Lc, LinkList La, LinkList Lb) {
    LinkNode *preC = Lc;
    LinkNode *curC = Lc->next;

    while(curC != NULL){
        ElemType e = curC->data;

        if(IsElementInLinkList(La, e) && IsElementInLinkList(Lb, e)){
            preC->next = curC->next;
            free(curC);
            curC = preC->next;
        } else{
            preC = curC;
            curC = curC->next;
        }
    }
}

image-20240728181040924

17. La 和 Lb 按值非递减，归并 La 和 Lb 得到新的单链表 Lc，使得 Lc 也按值非递减且不含重复元素，并占用原来的空间

// 1. 插入节点到链表并避免重复
void InsertNode(LinkList Lc, LinkNode *&pc, LinkNode *&node) {
    if (pc == Lc || pc->data != node->data) { // 避免重复元素
        pc->next = node;
        pc = node;
    }
    node = node->next;
}

// 2. 归并两个有序链表
void MergeLinkList(LinkList &La, LinkList &Lb, LinkList &Lc) {
    Lc = La;
    LinkNode *pa = La->next;
    LinkNode *pb = Lb->next;
    LinkNode *pc = Lc;

    while (pa != NULL && pb != NULL) {
        if (pa->data < pb->data) {
            InsertNode(Lc, pc, pa);
        } else if (pa->data > pb->data) {
            InsertNode(Lc, pc, pb);
        } else { // pa->data == pb->data
            InsertNode(Lc, pc, pa);
            LinkNode *temp = pb;
            pb = pb->next;
            free(temp); // 释放重复元素节点
        }
    }

    // 插入剩余元素
    while (pa != NULL) {
        InsertNode(Lc, pc, pa);
    }

    while (pb != NULL) {
        InsertNode(Lc, pc, pb);
    }

    // 释放 Lb 头结点
    free(Lb);
    Lb = NULL;

    // 设置 Lc 尾节点的 next 为 NULL
    pc->next = NULL;
}

image-20240728181304210

18. 带头单链表中所有元素的数据值按递增顺序排列，删除链表中大于 min 且小于 max 的元素

void DeleteRange(LinkList &list, ElemType min, ElemType max) {
    LinkNode *prev = list;
    LinkNode *current = list->next;

    while (current != NULL) {
        if (current->data > min && current->data < max) {
            prev->next = current->next;
            free(current);
            current = prev->next;
        } else {
            prev = current;
            current = current->next;
        }
    }
}

image-20240728181409578

19. 链表冒泡排序

void BubbleSortLinkList(LinkList list) {
    // 如果链表为空或只有一个节点，无需排序
    if (list == NULL || list->next == NULL) {
        return;
    }

    int isSwapped = 1; // 用于标记在一次遍历中是否进行了交换
    LinkNode *current; // 当前遍历的节点指针
    LinkNode *lastSorted = NULL; // 标记已排序部分的起始位置

    // 当在某次完整遍历中未发生交换时，排序完成
    while (isSwapped) {
        isSwapped = 0; // 每次遍历开始时重置交换标志
        current = list->next; // 从第一个实际数据节点开始

        // 内层循环遍历链表，直到已排序部分为止
        while (current->next != lastSorted) {
            // 如果当前节点的值大于下一节点的值，则交换它们
            if (current->data > current->next->data) {
                ElemType temp = current->data;
                current->data = current->next->data;
                current->next->data = temp;
                isSwapped = 1; // 标记发生了交换
            }
            current = current->next; // 移动到下一个节点
        }
        // 将最后排序好的节点设置为新的已排序部分的起始位置
        lastSorted = current;
    }
}

image-20240729163123370

20. 链表插入排序

void InsertionSortLinkList(LinkList list) {
    // 创建一个新的链表头用于存放已排序部分
    LinkNode *sortedHead = (LinkNode *)malloc(sizeof(LinkNode));
    sortedHead->next = NULL;

    // 逐个处理原链表中的节点并插入到新的链表中
    LinkNode *current = list->next;
    while (current != NULL) {
        LinkNode *next = current->next; // 记录下一个节点
        LinkNode *prev = sortedHead; // 从已排序部分的头开始
        LinkNode *sorted = sortedHead->next;

        // 找到插入位置
        while (sorted != NULL && sorted->data < current->data) {
            prev = sorted;
            sorted = sorted->next;
        }

        // 插入节点
        current->next = sorted;
        prev->next = current;

        // 移动到下一个节点
        current = next;
    }

    // 将原链表的头指针指向新的已排序链表
    list->next = sortedHead->next;
    free(sortedHead);
}

image-20240729170542638

21. 两个单词有相同的后缀时可共享相同后缀的存储空间，例如："act"和"dict"，如下图所示。设 La 和 Lb 分别指向两个单词所在单链表的头结点，链表结点结构为（data,next），设计算法查找公共后缀的起始位置。如图中标注的阴影数据结点部分为"act"和"dict"公共后缀的起始位置

image-20240729171025886

LinkNode *FindCommonSuffixStart(LinkList La, LinkList Lb) {
    if(La == NULL || Lb == NULL){
        return NULL;
    }

    LinkNode *p1 = La;
    LinkNode *p2 = Lb;

    while(p1 != p2){
        p1 = p1 == NULL ? Lb : p1->next;
        p2 = p2 == NULL ? La : p2->next;
    }

    return p1;
}

22. 设计一个算法，判断 Lb 是否为 La 的子链，子链的定义为：Lb 中的从前到后的所有节点的数据域都按照原有顺序出现在 La 中

bool IsSubLinkList(LinkList La, LinkList Lb) {
    LinkNode *pa = La->next;
    LinkNode *pb = Lb->next;
    LinkNode *start = La->next;

    while (start != NULL) {
        pa = start;
        pb = Lb->next;
        while (pa != NULL && pb != NULL && pa->data == pb->data) {
            pa = pa->next;
            pb = pb->next;
        }
        if (pb == NULL) {
            return true; // 完全匹配
        }
        start = start->next;
    }
    return false; // 未找到匹配
}

23. 将所有小于 x 的元素都排在其前面，所有大于 x 的元素都排在其后面

void PartitionLinkList(LinkList &list, ElemType x) {
    LinkNode *lessDummy = (LinkNode *)malloc(sizeof(LinkNode));
    LinkNode *greaterDummy = (LinkNode *)malloc(sizeof(LinkNode));
    lessDummy->next = NULL;
    greaterDummy->next = NULL;

    LinkNode *less = lessDummy;
    LinkNode *greater = greaterDummy;
    LinkNode *current = list->next;

    while (current != NULL) {
        if (current->data < x) {
            less->next = current;
            less = current;
        } else {
            greater->next = current;
            greater = current;
        }
        current = current->next;
    }

    // 连接两个链表
    less->next = greaterDummy->next;
    greater->next = NULL;

    // 更新原链表的头节点
    list->next = lessDummy->next;

    // 释放虚拟头节点
    free(lessDummy);
    free(greaterDummy);
}

24. 给定一个单链表 L，表示为：L0 → L1 → … → Ln - 1 → Ln，请将其重新排列后变为：L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …，不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

// 找到链表的中间节点
LinkNode *FindMiddleNode(LinkList list) {
    LinkNode *slow = list;  // 慢指针
    LinkNode *fast = list;  // 快指针

    // 快指针每次移动两步，慢指针每次移动一步
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 当快指针到达链表末尾时，慢指针正好到达链表中间
    return slow;
}

// 反转链表
LinkNode *ReverseLinkList(LinkNode *head) {
    LinkNode *pre = NULL;  // 前一个节点
    LinkNode *cur = head;  // 当前节点

    // 反转链表
    while (cur != NULL) {
        LinkNode *next = cur->next;  // 保存下一个节点
        cur->next = pre;             // 当前节点指向前一个节点
        pre = cur;                   // 前一个节点移动到当前节点
        cur = next;                  // 当前节点移动到下一个节点
    }

    // 返回反转后的链表头节点
    return pre;
}

// 合并两个链表
void MergeList(LinkNode *list1, LinkNode *list2) {
    while (list1 != NULL && list2 != NULL) {
        LinkNode *p1 = list1->next;  // 保存 list1 的下一个节点
        LinkNode *p2 = list2->next;  // 保存 list2 的下一个节点

        list1->next = list2;          // list1 的下一个节点指向 list2
        list1 = p1;                  // list1 移动到下一个节点

        if (list1 != NULL) {         // 如果 list1 不为空
            list2->next = list1;     // list2 的下一个节点指向 list1
        }
        list2 = p2;                  // list2 移动到下一个节点
    }
}

// 重新排列链表
void ReorderLinkList(LinkList &list) {
    if (list == NULL) {
        return;                      // 如果链表为空，直接返回
    }

    LinkNode *mid = FindMiddleNode(list);  // 找到链表的中间节点
    LinkNode *p1 = list->next;       // 链表的前半部分
    LinkNode *p2 = mid->next;     // 链表的后半部分
    mid->next = NULL;                 // 将链表分成两部分

    p2 = ReverseLinkList(p2);        // 反转链表的后半部分
    MergeList(p1, p2);               // 合并两个链表
}

25. 建立带头结点的循环单链表

// 初始化链表
bool InitLinkList(LinkList &list) {
    list = (LinkNode *)malloc(sizeof(LinkNode));
    if (list == NULL) {
        return false;
    }
    list->next = list;
    return true;
}

// 尾插法创建链表
void CreateLinkListByTailInsert(LinkList &list, ElemType elems[], int n) {
    InitLinkList(list);
    LinkNode *tail = list;
    for (int i = 0; i < n; i++) {
        LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
        newNode->data = elems[i];
        newNode->next = tail->next;
        tail->next = newNode;
        tail = newNode;
    }
}

26. 设计一个算法，将一个带头结点的循环单链表中所有结点的链接方向逆转

void ReverseLinkList(LinkList &list){
    LinkNode *pre = list;
    LinkNode *cur = list->next;
    LinkNode *next;

    while(cur != list){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }

    // 原来的最后一个节点成为新的头结点
    list->next = pre; 
}

27. 设计一个算法将循环单链表左移 k 个结点

void LeftShiftLinkList(LinkList &list, int k) {
    if (list == NULL || list->next == list) {
        return;
    }

    // 找到链表的长度
    LinkNode *tail = list;
    int length = 0;
    while (tail->next != list) {
        tail = tail->next;
        length++;
    }

    // 如果 k >= length，则等效于 k % length
    k = k % length;
    if (k == 0) {
        return;
    }

    // 找到新的头结点和尾结点
    LinkNode *newTail = list;
    for (int i = 0; i < k; i++) {
        newTail = newTail->next;
    }
    LinkNode *newHead = newTail->next;

    // 调整指针
    tail->next = list->next; // 原尾结点指向原头结点
    list->next = newHead;    // 头结点指向新头结点
    newTail->next = list;    // 新尾结点指向头结点

}

28. 设计算法将不带头结点的循环单链表中节点 p 的直接前驱删除

void DeletePredecessor(LinkNode *p) {
    LinkNode *prev = p;
    LinkNode *current = p->next;

    // 找到节点 p 的直接前驱节点
    while (current->next != p) {
        prev = current;
        current = current->next;
    }

    // 删除直接前驱节点
    prev->next = current->next;
    free(current);
}

29. 设计算法将一个含有数字、字母、其他字符组成的循环链表拆分成三个循环链表，每条链中只包含一种类型的字符

// 判断字符类型
enum CharType { DIGIT, ALPHA, OTHER };

CharType GetCharType(ElemType ch) {
    if (ch >= '0' && ch <= '9') {
        return DIGIT;
    } else if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {
        return ALPHA;
    } else {
        return OTHER;
    }
}

// 封装的插入操作
void InsertNode(LinkNode *&tail, ElemType data) {
    LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
    newNode->data = data;
    newNode->next = tail->next;
    tail->next = newNode;
    tail = newNode;
}

// 拆分链表
void SplitLinkList(LinkList source, LinkList &numList, LinkList &charList, LinkList &otherList) {
    InitLinkList(numList);
    InitLinkList(charList);
    InitLinkList(otherList);

    LinkNode *numTail = numList;
    LinkNode *charTail = charList;
    LinkNode *otherTail = otherList;

    LinkNode *current = source->next;
    while (current != source) {
        CharType type = GetCharType(current->data);
        if (type == DIGIT) {
            InsertNode(numTail, current->data);
        } else if (type == ALPHA) {
            InsertNode(charTail, current->data);
        } else {
            InsertNode(otherTail, current->data);
        }

        current = current->next;
    }
}

30. 已知 L 为一个单链表的头结点，设计算法将表中从 i 号结点到 m 号结点构成一个逆置的循环链表

// 找到第 i 个节点的前一个节点
LinkNode *FindPrevNode(LinkList list, int i) {
    LinkNode *pre = list;
    // 遍历找到第 i 个节点的前一个节点
    for (int j = 1; j < i; j++) {
        pre = pre->next;
    }
    return pre;
}

// 逆置从第 i 个节点到第 m 个节点并构成循环链表
LinkNode *ReverseAndFormCircular(LinkList &list, int i, int m) {
    LinkNode *preI = FindPrevNode(list, i); // 找到第 i 个节点的前一个节点
    LinkNode *preM = FindPrevNode(list, m); // 找到第 m 个节点的前一个节点

    LinkNode *lastM = preM->next; // 第 m 个节点
    LinkNode *p = preI->next; // 第 i 个节点
    preI->next = lastM->next; // 从链表中删除第 i 到第 m 节点
    lastM->next = NULL; // 断开第 m 个节点

    LinkNode *rL = (LinkNode *)malloc(sizeof(LinkNode));
    rL->next = rL; // 初始化循环链表

    // 逆置并构建循环链表
    while (p != NULL) {
        LinkNode *next = p->next;
        p->next = rL->next;
        rL->next = p;
        p = next;
    }

    return rL;
}

31. 已知 La 和 Lb 分别为两个循环单链表的头节点指针，m 和 n 分别为 La 和 Lb 中数据节点的个数，设计时间复杂度最小的算法将两个链表合并成一个带头的循环单链表

void combine(LinkList La, LinkList Lb, int m, int n){
    LinkNode *pShort = NULL;
    LinkNode *pLong = NULL;

    if(m > n){
        pShort = Lb;
        pLong = La;
    } else if{
        pShort = La;
        pLong = Lb;
    }

    LinkNode *cur = pShort->next;
    while(cur != pShort){
        LinkNode *next = cur->next;

        cur->next = pLong->next;
        pLong->next = cur;

        cur = next;
    }
    free(pShort);
}

32. 请设计一种数据结构来存储带头结点的循环单链表 La 和 Lb，使得两链合并时的效率尽可能高

// La 链和 Lb 链使用带尾结点指针的循环单链表
void combine(LinkNode &Ta, LinkNode &Tb){
    LinkNode *pHeadLa = Ta->next;
    LinkNode *pHeadLb = Tb->next;

    Ta->next = pHeadLb->next;
    Tb->next = pHeadLa->next;
    free(pHeadLb);
    Ta = Tb;
}
🌟 如果您喜欢我的文章，欢迎赞赏支持，您的支持是我创作的最大动力！🌟
🖋 作者：Enndfp
🔗链接：https://blog.enndfp.cn
📜版权声明：您可以自由转载，但请务必注明原文地址，感谢您的尊重与支持~
数据结构
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
图

							
							

							
二叉树

							
							

							
C语言程序设计

							
							

							
顺序表