37.2° Blog

1. 打印循环单链表

问题

打印循环单链表

算法思想

• 注意终止条件为pNode != L

代码

void printCircleList(LinkList L)
{
    printf("------------printf start------------\n");
    LinkNode* pNode = L->next;
    while (pNode != L)
    {
        printf("%d ", pNode->data);
        pNode = pNode->next;
    }
    printf("\n------------printf end------------\n");
}

2. 头插法创建循环单链表

问题

建立带头节点的循环单链表

算法思想

• 注意初始化时需将L->next = L。

代码

void createCircleList(LinkList& L, ElemType* arr, int arrLength)
{
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = L;
    LinkNode* pNode = NULL;
    for (int i = 0; i < arrLength; i++)
    {
        pNode = (LinkNode*)malloc(sizeof(LinkNode));
        pNode->data = arr[i];
        // 头插法
        pNode->next = L->next;
        L->next = pNode;
    }
}

2. 尾插法构造循环单链表

问题

创建尾指针指向的循环单链表

算法思想

• 注意更新尾指针

代码

void createTailCircleList(LinkList& L, ElemType* arr, int arrLength)
{
    // 创建头节点
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = L;
    // 使用尾插法构建单链表
    LinkNode* tailNode = L;
    LinkNode* tmpNode = NULL;
    for (int i = 0; i < arrLength; i++)
    {
        tmpNode = (LinkNode*)malloc(sizeof(LinkNode));
        tmpNode->data = arr[i];
        // 尾插法
        tmpNode->next = tailNode->next;
        tailNode->next = tmpNode;
        // 更新尾指针
        tailNode = tmpNode;
    }
}

4.循环单链表反转

问题

将一个带头结点的循环单链表中所有的链接方向反转

算法思想

• 构建新的循环链表
• 依次将旧链表中的结点使用头插法插入新链表
• 注意终止条件

代码

void reverseCircleList(LinkList& L)
{
    // 指向第一个数据节点
    LinkNode* pNode = L->next;
    // 新建一个空的循环链表
    L->next = L;
    LinkNode* tmpNode = NULL;
    while (pNode != L)
    {
        // 保存待插入结点
        tmpNode = pNode;
        // 更新pNode
        pNode = pNode->next;
        // 将结点使用头插法插入新的循环链表中
        tmpNode->next = L->next;
        L->next = tmpNode;
        
    }
}

5. 循环左移k个结点

问题

设计算法将不带头结点的循环单链表左移k个结点

算法思想

不带头结点循环单链表，左移k位后，循环链表中的第k+1个元素将会成为链表中第一个数据节点，所以只需将头结点指向第K+1个结点，就能实现左移k位。

代码

void moveElemCircleList(LinkList& L, int k)
{
    if (L == NULL)
        return;
    LinkNode* pNode = L;
    int count = 1;
    while (count <= k)
    {
        pNode = pNode->next;
        count++;
    }
    // 左移k个结点后，k+1个结点即为循环单链表中第一个数据结点
    L = pNode;
}

带头结点循环单链表左移

带头节点的循环单链表先把头节点摘下来，链成不带头节点的循环单链表，在不带头节点的循环单链表上操作，最后将链表头结点加入

void moveElemCircleList2(LinkList& L, int k)
{
    // 将头节点取下
    LinkNode* pNode = L->next;
    // 找到链表的最后一个结点
    while (pNode->next != L)
    {
        pNode = pNode->next;
    }
    // 将头结点去掉，此时为不带头结点循环单链表
    pNode->next = L->next;
    // pNode继续指向第一个结点
    pNode = pNode->next;
    int count = 1;
    // 记住一下前驱节点，方便把头节点加进去
    LinkNode* preNode = NULL;
    while (count <= k)
    {
        preNode = pNode;
        pNode = pNode->next;
        count++;
    }
    // 将头节点加入链表
    preNode->next = L;
    L->next = pNode;
}

6. 删除结点p的前驱

问题

设计算法将循环单链表中结点p的直接前驱删除

算法思想

• 先找p的前驱节点，同时保存p前驱的前驱
• 删除p的前驱

代码

void deleteCircleListPreNode(LinkList L, LinkNode* p)
{
    LinkNode* pNode = L->next;
    LinkNode* preNode = L;
    // 从pNode开始查找p的前驱结点
    while (pNode->next != p)
    {
        preNode = pNode;
        pNode = pNode->next;
    }
    // 删除p的前驱结点
    preNode->next = pNode->next;
    free(pNode);
}

7.逆置部分单链表

问题

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

算法思想

• 将查找链表中第i个结点的前驱封装为一个函数
• 将单链表中的第i个和第m个结点的前驱取出来；
• 把第i到m结点从单链表中取出来，用头插法插入新的循环单链表中。

代码

查找第i个结点的前驱

LinkNode* getNodePre(LinkList L, int i)
{
    LinkNode* pNode = L->next;
    LinkNode* preNode = L;
    int count = 0;
    while (pNode != NULL)
    {
        count++;
        if (count == i)
            return preNode;
        preNode = pNode;
        pNode = pNode->next;
    }
}

处理单链表及新建循环单链表

LinkList composeCircleList(LinkList L, int i, int m)
{
    LinkNode* preNodeI = getNodePre(L, i);
    LinkNode* preNodeM = getNodePre(L, m);
    // 取出第m个结点
    LinkNode* pNode = preNodeI->next;    
    // 将原来的单链表链起来
    preNodeI->next = preNodeM->next->next;
    // 将第m个结点的后继置为NULL
    preNodeM->next->next = NULL;
    // 新建循环单链表
    LinkList circleLst = (LinkNode*)malloc(sizeof(LinkNode));
    circleLst->next = circleLst;
    // 头插法将取出来的单链表插入新的循环单链表
    while (pNode != NULL)
    {
        LinkNode* tmpNode = pNode;
        pNode = pNode->next;
        tmpNode->next = circleLst->next;
        circleLst->next = tmpNode;
    }

    return circleLst;
}

8. 循环单链表合并

问题

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

算法思想

• 找到两个链表中的最长链和最短链；
• 依次访问最短链，使用头插法插入较长链中；

代码

void combineCircleList(LinkList La, LinkList Lb, int m, int n)
{
    // 指向较长的链
    LinkNode* pShort = m > n ? Lb : La;
    // 指向较短的链
    LinkNode* pLong = m > n ? La : Lb;
    LinkNode* pNode = pShort->next;
    LinkNode* tmpNode = NULL;
    // 依次访问较短链中的数据，并插入较长链中
    while (pNode != pShort)
    {
        tmpNode = pNode;
        pNode = pNode->next;
        // 头插法
        tmpNode->next = pLong->next;
        pLong->next = tmpNode;
    }
    // 释放较短链头节点
    free(pShort);
}

9.带尾指针的循环单链表

思想

当尾部操作比较频繁时，可以在表中设置尾指针，而不设置头指针。这样就避免了频繁的从头结点搜索尾结点的情况。

注意：单链表中头结点不存在前驱，尾结点也不存在后继。但是在循环单链表中，包括头结点和尾结点在内，任意结点都会有前驱和后继。

代码

L 是链表的尾指针

void createTailPointCircleList(LinkList& L, ElemType* arr, int arrLength)
{
    // 创建头节点
    L = (LinkNode*)malloc(sizeof(LinkNode));
    L->next = L;
    // 使用尾插法构建单链表
    LinkNode* tmpNode = NULL;
    for (int i = 0; i < arrLength; i++)
    {
        tmpNode = (LinkNode*)malloc(sizeof(LinkNode));
        tmpNode->data = arr[i];
        // 尾插法
        tmpNode->next = L->next;
        L->next = tmpNode;
        // 更新尾指针
        L = tmpNode;
    }
}

输出函数

void printTailList(LinkList L)
{
    // pHead指向头结点
    LinkNode* pHead = L->next;
    // pNode指向头结点的后继
    LinkNode* pNode = pHead->next;
    while (pNode != pHead)
    {
        printf("%d ", pNode->data);
        pNode = pNode->next;
    }
    printf("\n--------end-------\n");
}

补充

问题

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

算法思想

• La和Lb使用带尾结点指针的循环单链表
• 将La的尾指针指向Lb的第一个数据节点，然后将Lb链的尾结点指针指向La链的结点

代码

void combineCircleList(LinkList& La, LinkList& Lb)
{
    // 指向La的头结点
    LinkNode* pHeadLa = La->next;
    // 指向Lb的头结点
    LinkNode* pHeadLb = Lb->next;
    // La中的尾结点指针指向Lb的第一个数据结点
    La->next = pHeadLb->next;
    // Lb尾结点指针指向La的头结点
    Lb->next = pHeadLa;
    // 释放Lb的头结点
    free(pHeadLb);
    // 修改La的尾指针
    La = Lb;
}

测试

int arr[] = { 0,1,2,1,0};
int arrLength = 5;
LinkList La;
createTailPointCircleList(La, arr, arrLength);
printTailList(La);
LinkList Lb;
createTailPointCircleList(Lb, arr, arrLength);
combineCircleList(La, Lb);
printTailList(La);