37.2° Blog

1.第j+len个结点

问题

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

算法思想

• 无头结点链表操作比较麻烦，可以对两个链表分别增加两个头结点，待完成操作后，再将头结点释放。
• 删除结点，需要找到该节点的前驱，可以将找第j个结点的前驱封装为一个函数。
• 在La中获得第ja个结点的前驱pre以及第len+ja-1个结点的后继pSucc，
• 接着将pSucc结点更新为pre结点之后，及从La链中移出包含第ja到ja+len-1个结点的数据链，最后将整条链插入Lb的jb前。

代码

// 在链表L中找到第ith个结点和前驱的地址
void getIthNode(LinkList L, int ith, LinkNode* preJthNode, LinkNode* pJthNode)
{
    LinkNode* pMove = L->next;
    LinkNode* preMove = L;
    // 从第0个结点开始访问
    int count = 0;
    while (pMove != NULL && count < ith)
    {
        preMove = pMove;
        pMove = pMove->next;
        count++;
    }
    preJthNode = preMove;
    pJthNode = pMove;
}
void operateLinkList(LinkList& La, LinkList& Lb, int j, int len)
{
    // 没有头结点不好操作，给链表添加头结点
    LinkNode* headLa = (LinkNode*)malloc(sizeof(LinkNode));
    LinkNode* headLb = (LinkNode*)malloc(sizeof(LinkNode));
    headLa->next = La;
    headLb->next = Lb;
    
    // 用于保存La中第j个结点前驱的地址
    LinkNode* preJthNodeLa = NULL;
    // 用于保存La的第j各结点的地址
    LinkNode* pJthNodeLa = NULL;
    // 带头结点La中查找第j个结点及后继
    getIthNode(headLa, j, preJthNodeLa, pJthNodeLa);

    // 用于保存La中j+len个结点的地址和前驱的地址
    LinkNode* preLenthNodeLa = NULL;
    LinkNode* pLenthNodeLa = NULL;
    // 从带头结点查找到j+len个结点的地址及前驱地址
    getIthNode(preJthNodeLa, j+len-1, preLenthNodeLa, pLenthNodeLa);
    // 用于保存Lb中j个结点的地址和前驱的地址
    LinkNode* preJthNodeLb = NULL;
    LinkNode* pJthNodeLb = NULL;
    getIthNode(headLb, j, preJthNodeLb, pJthNodeLb);

    // 1、从La中删除从第j个到j+len个的结点
    preJthNodeLa->next = pLenthNodeLa->next;
    // 2、La链中的第j+len个结点的指针指向Lb中第j个结点
    pLenthNodeLa->next = pJthNodeLb;
    // 3、La链中的第j个结点的前驱指向La中的第j个结点
    preJthNodeLb->next = pJthNodeLa;

    // 操作完成，是否两条链的头结点
    La = headLa->next;
    free(headLa);
    La = headLb->next;
    free(headLb);
}

2.前n个字符对称

问题

设单链表表头指针为L，结点数据域为字符，设计时间复杂度最低的算法判断前n个字符是否中心对称，例如：xyx，xyyx均对称。

算法思想

• 使用两个指针，快指针和慢指针，快指针每次走两步，慢指针每次走一步；
• 当快指针指向链表末尾时，慢指针为链表中间；
• 慢指针继续走后半部分链表，并将后半部分链表反转，存在pMidlle结点中；
• 使用pHead指针，指向链表的头结点（存数据的）；
• 对比pMiddle和pHead指针中的数据是否相同，若不同，返回不对称；遍历完成则返回对称。

代码

int isSymmetric(LinkList L)
{
    LinkNode* pSlow = L;
    LinkNode* pFast = L;
    // 快指针走两步，慢指针走一步
    // 当快指针到链尾部，则慢指针到链表的中间
    while (pFast->next != NULL && pFast->next->next != NULL)
    {
        pSlow = pSlow->next;
        pFast = pFast->next->next;
    }
    /////////// 注意，将链表分为两个部分
    /////////// L为头结点的前半部分，和pSlow开始的后半部分
    LinkNode* preSlow = pSlow;
    pSlow = pSlow->next;
    preSlow->next = NULL;

    // 后继，防止断链
    LinkNode* pMiddle = NULL;
    LinkList tmpNode;
    // 慢指针继续走，将后半部分链反转
    // 链头存在 pMiddle 结点中
    while (pSlow != NULL)
    {
        tmpNode = pSlow;
        pSlow = pSlow->next;
        // 不带头结点的头插法
        tmpNode->next = pMiddle;
        pMiddle = tmpNode;
    }
    // 链头指针赋给pHead
    LinkNode* pHead = L->next;
    // 比较链头、链中指针的元素，直至结束
    while (pMiddle != NULL && pHead != NULL)
    {
        if (pMiddle->data != pHead->data)
        {
            return false;
        }
        pMiddle = pMiddle->next;
        pHead = pHead->next;
    }

    return true;
}

3. 删除相同结点

问题

从非递减有序单链表中，删除值相同的多余元素。

算法思想

• 依次访问链表中的每一个结点；
• 比较当前结点的数据和下一个结点的数据大小；
• 如果相同，则删除下一个结点；
• 如果不同，则指向下一个结点。

注意：边界条件，循环条件

代码

一个链表涉及相同结点的操作，一定要使用前驱和后继的这种访问规则。

// 从非递减有序单链表中，删除值相同的多余元素。
void deleteSimilarElem(LinkList L)
{
    // 指向第一个数据结点
    LinkNode* preNode = L->next;
    // 访问每一个数据结点
    while (preNode != NULL && preNode->next != NULL)
    {
        // 相同，则进行删除
        if (preNode->data == preNode->next->data)
        {
            LinkNode* tmpNode = preNode->next;
            preNode->next = preNode->next->next;
            free(tmpNode);
        }
        // 不同，则指向下一个结点
        else
            preNode = preNode->next;
    }
}

4. 比x小的结点数量

问题

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

算法思想

• 依次遍历结点，大于x的结点没必要遍历；
• 注意重复元素的排除

代码

int lessValueNumber(LinkList L, ElemType x)
{
    int count = 0;
    // 当前结点：指向数据
    LinkNode* pNode = L->next;
    // 前驱结点
    LinkNode* preNode = L;
    // 访问每一对前驱后继，p不为空，且结点数据小于x
    while (pNode != NULL && pNode->data < x)
    {
        // 数值与前驱结点不相同时，计数加1
        if (preNode == L || preNode->data != pNode->data)
            count++;
        // 更新结点
        preNode = pNode;
        pNode = pNode->next;
    }
    return count;
}

5. 两表删除相同元素

问题

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

算法思想

• 指针pNodeLa和pNodeLb分别指向两个链表的第一个元素；
• 较大值的指针原地等待，移动结点值较小的指针；
• 直到pNodeLa和pNodeLb指针指向结点的值相等；
• 在La中删除相同的结点，继续比较值的大小。

代码

void deleteSimilar2List(LinkList La, LinkList Lb)
{
    LinkNode* pNodeLa = La->next;
    LinkNode* preNodeLa = La;
    LinkNode* pNodeLb = Lb->next;
    while (pNodeLa != NULL && pNodeLb != NULL)
    {
        // pNodeLa 小于 pNodeLb
        if (pNodeLa->data < pNodeLb->data)
        {
            // 访问La的下一个结点
            preNodeLa = pNodeLa;
            pNodeLa = pNodeLa->next;
        }
        // pNodeLa 大于 pNodeLb
        else if (pNodeLa->data > pNodeLb->data)
        {
            // 访问Lb的下一个结点
            pNodeLb = pNodeLa->next;
        }
        else
        {
            // 删除La中相同的结点
            preNodeLa->next = pNodeLa->next;
            // 释放空间
            free(pNodeLa);
            // 指向下一个节点
            pNodeLa = preNodeLa->next;
        }
    }
}

6. 三表删除相同元素

问题

已知La，Lb，Lc是三个链表，其元素按递增顺序排序，每个表中均无重复数据，设计算法在表La中删除同时出现在Lb和Lc中的元素。。

算法思想

• 先查找Lb和Lc中相同的元素；
• 若查找到相同元素，将La工作指针移动到小于这个元素的位置；
• 判断La当前工作指针的元素是否等于这个元素；
• 若相等，在La中删除这个元素；若不相等，跳过；
• 向后移动Lb和Lc的工作指针
• 直到其中的一条链遍历完成。

代码

void deleteSimilar3List(LinkList La, LinkList Lb, LinkList Lc)
{
    LinkNode* pCurLa = La->next;
    LinkNode* preCurLa = La;
    LinkNode* pCurLb = Lb->next;
    LinkNode* pCurLc = Lc->next;
    while (pCurLa != NULL && pCurLb != NULL && pCurLc != NULL)
    {
        // pNodeLb 小于 pNodeLc，向后移动pNodeLb指针
        if (pCurLb->data < pCurLc->data)
            pCurLb = pCurLb->next;
        // pNodeLb 大于 pNodeLc，向后移动pNodeLc指针
        else if (pCurLb->data > pCurLc->data)
            pCurLc = pCurLc->next;
        // 两链中找到相同结点
        else
        {
            // 搜索大于等于e的结点
            while (pCurLa != NULL && pCurLa->data < pCurLc->data)
            {
                // 更新当前结点及前驱
                preCurLa = pCurLa;
                pCurLa = pCurLa->next;
            }
            // 相同，进行删除
            if (pCurLa->data == pCurLc->data)
            {
                preCurLa->next = pCurLa->next;
                free(pCurLa);
                pCurLa = preCurLa->next;
            }
            // 删除完成后，同时移动pNodeLb和pNodeLc
            pCurLc = pCurLc->next;
            pCurLb = pCurLb->next;
        }
    }
}

7. 归并两表删除重复元素

问题

La和Lb按值非递减，归并La和Lb，得到新的单链表Lc， 使得Lc也按值非递减且不含重复元素，

算法思想

• 释放Lb头结点，Lc抢占La的头结点；
• 从La和Lb中，选取最小的元素尾插法插入Lc中；
• 插入的时候注意Lc表尾元素与待插入结点值是否相同，若相同，则释放待插入结点；
• 将剩余的La和Lb并入Lc中

代码

// 尾插法插入元素
void insertElem(LinkNode*& tailLc, LinkNode* pNode)
{
    // 若值相同，释放空间
    if (pNode->data == tailLc->data)
        free(pNode);
    else
    {
        // 插入Lc表尾
        pNode->next = tailLc->next;
        tailLc->next = pNode;
        tailLc = tailLc->next;
    }
}
void combineSorted2List(LinkList& La, LinkList& Lb, LinkList& Lc)
{
    LinkNode* pCurLa = La->next;
    LinkNode* pCurLb = Lb->next;
    // Lb的头结点释放
    free(Lb);
    // Lc抢占La的头结点
    Lc = La;
    Lc->next = NULL;
    // Lc的链尾指针，方便后续插入
    LinkNode* tailLc = Lc;
    // 临时结点
    LinkNode* tmpNode = NULL;
    while (pCurLa != NULL && pCurLb != NULL)
    {
        // 每次选取两个链中的最小结点插入到新链中
        if (pCurLa->data < pCurLb->data)
        {
            // 保存待插入结点
            tmpNode = pCurLa;
            // 从La中删除待插入结点
            pCurLa = pCurLa->next;
            // 插入
            insertElem(tailLc, tmpNode);
        }
        else
        {
            tmpNode = pCurLb;
            pCurLb = pCurLb->next;
            insertElem(tailLc, tmpNode);
        }
    }
    // 合并La的剩余结点
    while (pCurLa != NULL)
    {
        tmpNode = pCurLa;
        pCurLa = pCurLa->next;
        insertElem(tailLc, tmpNode);
    }
    // 合并Lb的剩余结点
    while (pCurLb != NULL)
    {
        tmpNode = pCurLb;
        pCurLb = pCurLb->next;
        insertElem(tailLc, tmpNode);
    }
}

8. 删除[min, max]直接的元素

问题

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

算法思想

• 先让工作指针指向第一个大于min的结点；
• 之后，删除每个大于min小于max的结点

代码

void deleteMinMaxNodes(LinkList L, int min, int max)
{
    // 指向第一个结点
    LinkNode* pNode = L->next;
    // 指向前驱
    LinkNode* preNode = L;
    // 找到第一个大于min的结点
    while (pNode != NULL)
    {
        // 如果找到，结束查找
        if (pNode->data > min && pNode->data < max)
        {
            // 删除结点，释放内存
            preNode->next = pNode->next;
            free(pNode);
            // 更新pNode指针，指向下一个
            pNode = preNode->next;
        }
        else if (pNode->data > max)
            break;
        else if (pNode->data < min)
        {
            preNode = pNode;
            pNode = pNode->next;
        }
    }
}

9. 链表冒泡排序

问题

对链表使用冒泡排序法

算法思想

• 不断从第一个结点往表尾扫描；
• 如果相邻前驱与后继结点存在逆序，就将前驱和后继结点数据交换，直到一趟链表中不存在逆序。

代码

void listBubleSort(LinkList L)
{
    // 一直扫描第一至倒数第二个结点，判断每个结点与后继
    while (1)
    {
        LinkNode* pNode = L->next;
        ElemType tmpElem;
        // 数据交换标志位，提升算法性能
        int isExchgeFlag = 0;
        // 访问每一对前驱和后继
        while (pNode != NULL && pNode->next != NULL)
        {
            // 判断是否逆序，如果逆序，则交换元素
            if (pNode->data > pNode->next->data)
            {
                tmpElem = pNode->data;
                pNode->data = pNode->next->data;
                pNode->next->data = tmpElem;
                isExchgeFlag = 1;
            }
            // 指针移动到下一个
            pNode = pNode->next;
        }
        if (isExchgeFlag == 0)
        {
            break;
        }
    }
}

10.链表插入排序

问题

设L为单链表头结点地址，其数据结点都是正整数，可能存在相同数值的结点，设计一个空间复杂度最低的算法，利用直接插入排序把该链表整理成有序链表，并将重复元素删除。

算法思想

• 构建一个含有头结点的空表L；
• 然后取链表的每个数据结点；
• 在L上查找待插入位置；
• 如果当前插入结点已经存在链表中了，则释放空间；
• 反之将其插入到对应的位置；
• 重复上述步骤，直到数据链中不存在待插入结点。

代码

void listInsertSort(LinkList L)
{
    // 构建一个新链，将每个结点插入到新链的合适位置
    LinkNode* pNodeData = L->next;
    L->next = NULL;
    while (pNodeData != NULL)
    {
        // 准备插入结点前一定将pNodeData向后移动一个位置，否则会断链
        LinkNode* tmpNode = pNodeData;
        pNodeData = pNodeData->next;
        
        // 固定的解题模板，寻找插入位置，
        // 一个移动指针，一个前驱保存插入位置
        LinkNode* pNode = L->next;
        LinkNode* preNode = L;
        // 在L中寻找插入位置
        while (pNode != NULL && tmpNode->data > pNode->data)
        {
            preNode = pNode;
            pNode = pNode->next;
        }
        // preNode在while循环跳出后即为插入位置，结点插入在preNode之后
        if (pNode != NULL && tmpNode->data == pNode->data)
            free(tmpNode);
        // 插入结点
        else
        {
            tmpNode->next = preNode->next;
            preNode->next = tmpNode;
        }
    }
}

11. 链表结点二分类

问题

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

算法思想

访问每一个数据结点，如果当前访问结点数据小于x，则将其插入到头结点；不断重复上述步骤，直到访问完所有数据结点。

代码

void listMoveElem(LinkList L, int x)
{
    // 指向第一个数据结点的后继结点
    LinkNode* pNode = L->next;
    // 指向前驱
    LinkNode* preNode = L;
    // 遍历L中所有数据结点
    while (pNode != NULL)
    {
        // 当前访问元素小于x，插入头结点之后
        if (pNode->data < x)
        {
            preNode->next = pNode->next;
            // 插入到头结点之后
            // 更新指针域
            pNode->next = L->next;
            L->next = pNode;
            pNode = preNode->next;
        }
        // 当前访问结点大于x
        else
        {
            // 更新preNode，指向新的前驱
            preNode = pNode;
            // 更新pNode后继，指向新的后继
            pNode = pNode->next;
        }
    }
}

12. 查找子链

问题

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

算法思想

• 从前往后访问La中的每一个结点，当前访问结点视为一轮子链查找的开始位置。
• 如果从当前访问结点开始与Lb中对应位置的结点全部匹配成功，停止查找；
• 如果在匹配的过程中比较的结点数据不符，则从La中下一个结点作为下一轮匹配开始的位置重新开始匹配；
• 直到La中所有结点全部访问完停止；

代码

bool isSubLinkList(LinkList La, LinkList Lb)
{
    // 没一轮比较开始的位置，第一轮从La的第一个结点开始
    LinkNode* pStartPosition = La->next;
    // 从比较位置开始，访问La的每一个结点
    LinkNode* pMoveLa = pStartPosition;
    // 在Lb中从前往后访问结点与La进行匹配
    LinkNode* pMoveLb = Lb->next;
    // 在第一轮匹配中，从前往后访问数据结点进行匹配
    while (pMoveLa != NULL && pMoveLb != NULL)
    {
        // 当前位置匹配成功，取后继结点进行下一次比较
        if (pMoveLa->data == pMoveLb->data)
        {
            pMoveLa = pMoveLa->next;
            pMoveLb = pMoveLb->next;
        }
        // 当前位置匹配不成功，开始下一轮匹配
        else
        {
            // La开始位置后移
            pStartPosition = pStartPosition->next;
            // 后移待匹配位置
            pMoveLa = pStartPosition;
            // 将Lb的工作指针后移
            pMoveLb = Lb->next;
        }
    }
    // 如果Lb为NULL，则匹配成功
    if (pMoveLb != NULL)
        return false;
    return true;
}

13. 查找公共后缀

问题

两个单词都有相同的后缀时可共享相同后缀的存储空间，例如，“act”和“dict”，设La和Lb分别为两个单词所在单链表的头结点，设计算法查找公共后缀的起始位置。

算法思想

• 将La的长度记为a， Lb的长度记为b；
• 移动较长链的工作指针abs(a-b)个结点，两个链工作指针后的结点数量一样；
• 比较两个结点的地址（数据），即找到公共点；
• 否则，重复上述步骤，直到遇到公共结点停止。

代码

// 获取链表长度
int getLength(LinkList L)
{
    int len = 0;
    LinkNode* pNode = L->next;
    while (pNode->next != NULL)
    {
        len++;
        pNode = pNode->next;
    }
    return len;
}
LinkNode* getCommonNode(LinkList La, LinkList Lb)
{
    int lengthLa = getLength(La);
    int lengthLb = getLength(Lb);
    LinkNode* pNodeLa = La;
    LinkNode* pNodeLb = Lb;
    // 将较长的链表工作指针向后移动，移动到和较短链表长度一样
    if (lengthLa - lengthLb > 0)
    {
        // 若La较长，移动La的工作指针
        int count = 0;
        while (count <= lengthLa - lengthLb)
        {
            pNodeLa = pNodeLa->next;
            count++;
        }
        pNodeLb = pNodeLb->next;
    }
    else
    {
        // 若Lb较长，移动Lb的工作指针
        int count = 0;
        while (count <= lengthLb - lengthLa)
        {
            pNodeLb = pNodeLb->next;
            count++;
        }
        pNodeLa = pNodeLa->next;
    }
    // 比较两个指针的结点是否相同
    // 注意：比较地址运行出错
    while (pNodeLa->data != pNodeLb->data)
    {
        pNodeLa = pNodeLa->next;
        pNodeLb = pNodeLb->next;
    }
    // 返回公共位置
    return pNodeLa;
}

14. 构造复杂链表

问题

长度为n的单链表L=(L1, L2, L3, ...., Ln)。设计时间复杂度和空间复杂度最少的算法将单链表转换为Lt=(L1, Ln, L2, Ln-1, ....)。

算法思想

• 使用快慢指针将链表分为两个部分；
• 快指针走两步，慢指针走一步，快指针到链接结尾则慢指针到链表中间；
• 慢指针继续走后半部分链表，并将后半部分链表反转，存在pMidlle结点中；
• 此时，pHead指针指向链表头结点，pMIddle指针指向反序的链表后半节点；
• 使用尾插法，依次将pHead指针的第一个元素和pMiddle指针的第一个元素插入L中；
• 直至pHead或pMiddle无元素即可

代码

void convertLinkList(LinkList L)
{
    LinkNode* pSlow = L;
    LinkNode* pFast = L;
    // 快指针走两步，慢指针走一步
    // 当快指针到链尾部，则慢指针到链表的中间
    while (pFast->next != NULL && pFast->next->next != NULL)
    {
        pSlow = pSlow->next;
        pFast = pFast->next->next;
    }
    /////////// 注意，将链表分为两个部分
    /////////// L为头结点的前半部分，和pSlow开始的后半部分
    LinkNode* preSlow = pSlow;
    pSlow = pSlow->next;
    preSlow->next = NULL;

    // 后继，防止断链
    LinkNode* pMiddle = NULL;
    LinkNode* tmpNode;
    // 慢指针继续走，将后半部分链反转
    // 链头存在 pMiddle 结点中
    while (pSlow != NULL)
    {
        tmpNode = pSlow;
        pSlow = pSlow->next;
        // 不带头结点的头插法
        tmpNode->next = pMiddle;
        pMiddle = tmpNode;
    }
    // 链头指针赋给pHead
    LinkNode* pHead = L->next;
    L->next = NULL;
    LinkNode* tailNode = L;
    // 依次使用尾插法，将pHead和pMiddle插入L中
    while (pHead != NULL && pMiddle != NULL)
    {
        printLisst(L);
        // 尾插法插入pHead的第一个结点
        tmpNode = pHead;
        pHead = pHead->next;
        tmpNode->next = tailNode->next;
        tailNode->next = tmpNode;
        tailNode = tailNode->next;

        // 尾插法插入pMiddle的第一个结点
        tmpNode = pMiddle;
        pMiddle = pMiddle->next;
        tmpNode->next = tailNode->next;
        tailNode->next = tmpNode;
        tailNode = tailNode->next;
    }
    // 插入剩余结点
    while (pHead != NULL)
    {
        tmpNode = pHead;
        pHead = pHead->next;
        tmpNode->next = tailNode->next;
        tailNode->next = tmpNode;
        tailNode = tmpNode;
    }
    while (pMiddle != NULL)
    {
        tmpNode = pMiddle;
        pMiddle = pMiddle->next;
        tmpNode->next = tailNode->next;
        tailNode->next = tmpNode;
        tailNode = tmpNode;
    }
}