数据结构之链表

墨蓝 2022-05-30 04:44 225阅读 0赞

链表：将很多块内存区域通过指针的形式连接起来。其中在每块没存区域都存储了上一块数据或者下一块数据的地址，链表的优点在于删除元素和添加元素都非常快速。为了写出鲁棒性好的程序，防御性编程很重。对于指针必须考虑当指针为空的情况，对于字符串考虑内容为空的情况。对于链表的题目大多数都是通过遍历解决的。

# 理解链表的练习题 #

## 1、求单链表中的倒数第k个节点 ##

> 输入一个键表，输出该链表中倒数第k个结点。为了符合人们的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。一个链表有6个结点，从头结点开始它们的值依次是 1 、 2、 3、 4、 5、 6。这个链表的倒数第3个结点是值为4的结点。

思路：删除倒数第k个节点，就是相当于删除从头到尾第n-k+1个节点。  
方法一：遍历两次，第一次获取链表长度，第二次删除节点。  
方法二：定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）正好是倒数第k个结点。下图可以看出打印倒数第k个节点，**那么到了最后p1比p2多走了k-1步。这样就很容易了**。  
![这里写图片描述][70]  
注意：  
1、考虑输入头结点为空。  
2、输入k为0，因为规定从1开始，输入0会直接崩溃，因为k-1产生。  
3、k大于链表节点个数。

struct ListNode *FindKthToTail(struct ListNode *pListHead , unsigned char k)
    {
        //防御性编程,头节点为空,k为0
        if(pListHead == NULL || k == 0)
            return NULL;
        struct ListNode *p1 = pListHead;
        struct ListNode *p2 = pListHead;
        //1、先走k-1步咯
        for(int i = 0 ; i < k - 1 ; i++){
            if(p1->pNext != NULL)//防止k比节点个数多的情况
                p1 = p1->pNext;
            else
                return NULL;
        }
        //2、再一起走到底咯
        while(p1->pNext != NULL){
            p1 = p1->pNext;
            p2 = p2->pNext;
        }
        return p2;
    }

## 2、从尾到头打印单链表 ##

思路：采用递归或者栈，一般可以通过递归解决的都是可以通过栈搞定。当使用递归的时候，递归层次过深，可能出现栈帧溢出的问题。所以利用栈搞定则更具鲁棒性。

/* 通过栈实现从尾到头 */
    void PrintListReverseWithStack(struct ListNode *head){
        std::stack<struct ListNode *> nodes;//定义栈
        if(head == NULL)//判断边界
            return ;
        while(head != NULL){
            nodes.push(head);//压栈
            head = head->pNext;//迭代
        }
        while(!nodes.empty()){
            printf("%4d " , nodes.top()->key);//取出元素
            nodes.pop();//弹出元素
        }
        printf("\n");
    }
    /* 通过递归实现从尾到头 */
    void PrintListReverseWithRecursion(struct ListNode *head){
       //用栈的思想考虑递归会容易一点
        if(head == NULL)//判断边界
            return ;
        if(head->pNext != NULL)//最后一个退出
            PrintListReverseWithRecursion(head->pNext);
        printf("%4d " , head->key);
    }

## 3、单链表反转 ##

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。  
思路：记住前一个结点和后一个节点的信息，然后遍历一次链表，遍历开始时候确定前一个节点和后一个节点信息都为空，在循环里面更新信息。  
注意：  
1、输入pListHead == NULL。  
2、输入链表只有一个节点。  
3、输入链表有多个节点。

struct ListNode *ReverseList(struct ListNode *pListHead)
    {
        //防御性编程,防止链表为空
        if(pListHead == NULL)
            return pListHead;
        //1.正常反转,记住当前节点的前一个节点和后一个节点,这里已经防御了只有一个节点的情况
        struct ListNode *CurrentNode = pListHead;//当前节点
        struct ListNode *PreNode = NULL;//前一个节点,初始化前一个节点为空
        struct ListNode *NextNode = NULL;//后一个节点
        while(CurrentNode != NULL){
            NextNode = CurrentNode->pNext;//更新后一个节点信息
            CurrentNode->pNext = PreNode;//反转当前节点,指向前一个节点
            if(NextNode == NULL)
                return CurrentNode;//如果到达链表尾,则直接返回.
            PreNode = CurrentNode;//更新前一个节点
            CurrentNode = NextNode;//更新当前一个节点
        }
    }

## 4、合并两个已排序的单链表 ##

题目：输入两个递增排序的链表，合并这两个链表并使新链表中结点仍然是按照递增排序的。  
![这里写图片描述][70 1]  
思路：采用递归方法，合并过程如下图  
![这里写图片描述][70 2]

struct ListNode *MergeListRecursive(struct ListNode *pListHead1 , struct ListNode *pListHead2)
    {
        struct ListNode *pMergeHead;//指向合并链表头部
        //防御性编程.
        if(pListHead1 == NULL)
            return pListHead2;
        else if(pListHead2 == NULL)
            return pListHead1;
        //1.比较键值,并递归下去
        if(pListHead1->key < pListHead2->key){
            pMergeHead = pListHead1;
            pMergeHead->pNext = MergeListRecursive(pListHead1->pNext , pListHead2);
        }else{
            pMergeHead = pListHead2;
            pMergeHead->pNext = MergeListRecursive(pListHead1 , pListHead2->pNext);
        }
        return pMergeHead;//返回对应的键
    }

## 5、单链表排序 ##

[https://www.cnblogs.com/TenosDoIt/p/3666585.html][https_www.cnblogs.com_TenosDoIt_p_3666585.html]  
快速排序重要的是切分思路：  
快排需要一个指针指向头，一个指针指向尾，然后两个指针相向运动并按一定规律交换值，最后找到一个支点使得支点左边小于支点，支点右边大于支点吗。如果是这样的话，对于单链表我们没有前驱指针，怎么能使得后面的那个指针往前移动呢？所以这种快排思路行不通滴，如果我们能使两个指针都往next方向移动并且能找到支点那就好了。怎么做呢？  
接下来我们使用快排的另一种思路来解答。我们**只需要两个指针p和q，这两个指针均往next方向移动，移动的过程中保持p之前的key都小于选定的key，p和q之间的key都大于选定的key，那么当q走到末尾的时候便完成了一次支点的寻找**。如下图所示：  
![这里写图片描述][70 3]

//单链表快速排序
    void swap(int *a , int *b)
    {
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    //切分思路区别于数组的切分思路
    struct ListNode *Partition(struct ListNode *pBegin , struct ListNode *pEnd)
    {
        struct ListNode *p = pBegin;
        struct ListNode *q = pBegin->pNext;
        while(q != pEnd){
            if(q->key < pBegin->key){
                p = p->pNext;
                swap( &p->key , &q->key );
            }
            q = q->pNext;
        }
        swap( &p->key , &pBegin->key );
        return p;//返回切分位置
    }
    
    //快速排序 O(logn)
    void QuickSort(struct ListNode *pBegin , struct ListNode *pEnd)
    {
        if(pBegin == pEnd)
            return ;
        struct ListNode *j = Partition(pBegin , pEnd);
        QuickSort(pBegin , j);
        QuickSort(j->pNext , pEnd);
    }
    
    //冒泡排序 O(n*n)
    void ListBubble(struct ListNode *pBegin)
    {
        if(pBegin == NULL || pBegin->pNext == NULL)
            return ;
        struct ListNode *i = pBegin;
        struct ListNode *j;
        for( ; i != NULL ; i = i->pNext)
            for(j = i->pNext ; j != NULL ; j = j->pNext){
                if(i->key > j->key)
                    swap( &i->key , &j->key );
            }
    }

int main(void){
        struct ListNode *ListHead = NULL;
        for(int i = 20 ; i >= 0 ; i -= 2)
            ListHead = InsertListTail(ListHead , i);
        PrintList(ListHead);
        QuickSort(ListHead , NULL);
        //ListBubble(ListHead);
        PrintList(ListHead);
        return 0;
    }

![这里写图片描述][70 4]

## 6、寻找单链表的中间节点 ##

思路：  
1、正常方法是，遍历一次链表，找出链表长度，然后取出中间节点。这种方法需要遍历两次，效果不好。  
2、使用快慢指针，开始快和慢指针全部指向首节点；然后快指针每次走两步，慢指针每次走一步，当`pFast == NULL//对应节点偶数个`或`pFast->pNext == NULL//对应节点为奇数个`，则遍历结束，返回慢节点。画个简单的图形就可以明白这个过程。  
注意：  
1、防御性编程，注意鲁棒性。  
2、尽可能遍历一遍链表就可以解决问题，这是我们喜欢的方式。

struct ListNode *SearchMid(struct ListNode *pListHead)
    {
        struct ListNode *pSlow = pListHead;
        struct ListNode *pFast = pListHead;
        //防御性编程
        if(pListHead == NULL)
            return NULL;
        //开始快慢遍历,pFast为空对应节点为奇数，则返回中间节点。pFast->pNext为空,对应节点为偶数，则返回中间两个节点的后一个。
        while(pFast != NULL && pFast->pNext != NULL){
            pFast = pFast->pNext->pNext;//走两步
            pSlow = pSlow->pNext;//走一步
        }
        return pSlow;//返回中间节点
    }

## 7、交换单链表任意两个元素 ##

## 8、求有环单链表中的环长、环起点、链表长 ##

[参考这里，很形象][Link 1]  
1、判断单链表是否有环：  
　　使用两个slow, fast指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。  
　　![这里写图片描述][70 5]

//判断链表是否有环
    struct ListNode *JudgeRing(struct ListNode *pListHead)
    {
        struct ListNode *pSlow = pListHead;
        struct ListNode *pFast = pListHead;
        //防御性编程
        if(pListHead == NULL)
            return NULL;
        while(1){
            //如果pFast先退出,那么就是没有环,如果fast退不出,那么就是有环
            if(pSlow->pNext != NULL && pFast->pNext != NULL && pFast->pNext->pNext != NULL){
                pFast = pFast->pNext->pNext;//走两步
                pSlow = pSlow->pNext;//走一步
            }else
                return NULL;
            if(pFast == pSlow)
                return pFast;
        }
    }

2、求有环单链表的环长：  
　　在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长，相当于在圆形操场同一起点两人跑步，下一次相遇，不是正好快的比慢的多跑一圈。  
　　设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2\*len步，相遇时多走了一圈：  
　　　　环长=2\*len-len。  
　　就是所谓的追击相遇问题。

int GetRingLength(struct ListNode *pListHead)
    {
        //防御性编程
        if(pListHead == NULL)
            return 0;
        struct ListNode *ringMeetNode = JudgeRing(pListHead);//判断是否有环,并记录相遇点
    
        if(ringMeetNode == NULL)
            return 0;//无环直接退出
        //有环,从相遇点在fast和slow走一遍就是再次相遇就是环长.
        int RingLength = 0;
        struct ListNode *pSlow = ringMeetNode;
        struct ListNode *pFast = ringMeetNode;
        while(1){
            pFast = pFast->pNext->pNext;
            pSlow = pSlow->pNext;
            RingLength++;
            if(pFast == pSlow)//相遇了,返回环长
                return RingLength;
        }
    }

3、求有环单链表的环连接点位置：  
　　第一次碰撞点Pos到连接点Join的距离 = 头指针到连接点Join的距离，因此，分别从第一次碰撞点Pos、头指针head开始走，相遇的那个点就是连接点。  
　　![这里写图片描述][70 6]  
在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。  
　　　　第一次相遇时，slow走的长度 S = LenA + x;  
　　　　第一次相遇时，fast走的长度 2S = LenA + n\*R + x;  
　　　　所以可以知道，LenA + x = n\*R;　　LenA = n\*R -x;此处令n=1，即可。

struct ListNode *GetRingJoinNode(struct ListNode *pListHead , int *length)
    {
        //防御性编程
        if(pListHead == NULL)
            return 0;
        struct ListNode *ringMeetNode = JudgeRing(pListHead);//判断是否有环,并记录相遇点
    
        if(ringMeetNode == NULL)
            return 0;//无环直接退出
        //求相交点,head和相遇点一起走,再次相遇则是相交点
        while (1) {
            ringMeetNode = ringMeetNode->pNext;
            pListHead = pListHead->pNext;
            (*length)++;//头节点到交点的长度
            if(ringMeetNode == pListHead)
                return ringMeetNode;
        }
    }

4、求有环单链表的链表长  
上述2中求出了环的长度；3中求出了连接点的位置，就可以求出头结点到连接点的长度。两者相加就是链表的长度。  
![这里写图片描述][70 7]  
5、例子–构造有环链表如下图：  
![这里写图片描述][Image 1]

int main(void)
    {
        //判断是否有环
        TempNode = JudgeRing(ListHead);
        printf("相遇节点值:%d\n" , TempNode == NULL ? 0 : TempNode->key);
    
        //求环长
        int RingLength = GetRingLength(ListHead);
        printf("环长:%d\n",RingLength);
    
        //求环交点及单链表长
        int HeadToJoinlength = 0;
        struct ListNode *RingJoinNode = GetRingJoinNode(ListHead,&HeadToJoinlength);
        printf("环起始点:%d,头节点到交点的长度:%d\n" , RingJoinNode->key ,HeadToJoinlength); ;
        printf("有环单链表长:%d\n" , RingLength + HeadToJoinlength);
        return 0;
    }

![这里写图片描述][Image 1]

## 9、判断两个单链表(无环)是否交叉 ##

![这里写图片描述][Image 1]  
判断是否相交突破口：如果两个没有换的链表相交于一点，那么在这个节点之后的所有节点都是两个链表共同拥有的，那么也就是最后一个节点一定是共有的。  
解法：很简单，先遍历一个链表，记住最后一个节点。然后遍历第二个，到最后一个节点时候和先前记住的节点比较。时间复杂度是O(length(list1) + length(list2))。而且仅仅用了一个变量，空间复杂度是O(1)。  
求交点突破口：判断出两个链表相交后就是判断他们的交点了。假设第一个链表长度为len1，第二个为len2，然后找出长度较长的，让长度较长的链表指针向后移动|len1 - len2| (len1-len2的绝对值)，然后在开始遍历两个链表，判断节点是否相同即可。  
给个相交链表的例子：  
![这里写图片描述][Image 1]

//判断单链表是否相交,并求出节点
    struct ListNode *JudgeCrossListAnd(struct ListNode *pListHead1 , struct ListNode *pListHead2)
    {
        //防御性编程
        struct ListNode *pTemp1 = pListHead1;
        struct ListNode *pTemp2 = pListHead2;
        if(pTemp1 == NULL || pTemp2 == NULL)
            return NULL;
        int List1Length = 0 , List2Length = 0;
        while(pTemp1->pNext != NULL){
       //找到List1尾部节点
            pTemp1 = pTemp1->pNext;
            List1Length++;
        }
        List1Length++;//求1长度
        while(pTemp2->pNext != NULL){
       //找到List1尾部节点
            pTemp2 = pTemp2->pNext;
            List2Length++;
        }
        List2Length++;//求2长度
        if(pTemp1 == pTemp2){
       //相交则求交点
            if(List1Length > List2Length){
       //链表1比链表2长,链表1先走
                for(int i = 0 ; i < (List1Length - List2Length) ; i++)
                       pListHead1 = pListHead1->pNext;
                while(pListHead1 != pListHead2){
                    pListHead1 = pListHead1->pNext;
                    pListHead2 = pListHead2->pNext;
                }
                return pListHead2;//找到交点
            }else{
       //链表1比链表2短,链表2先走
                for(int i = 0 ; i < (List2Length - List1Length) ; i++)
                       pListHead2 = pListHead2->pNext;
                while(pListHead1 != pListHead2){
                    pListHead1 = pListHead1->pNext;
                    pListHead2 = pListHead2->pNext;
                }
                return pListHead2;//找到交点
            }
        }
        else
            return NULL;
    }
    int main(void)
    {
        struct ListNode *ListHead1 = NULL,*ListHead2 = NULL,*ListHead3 = NULL;
        //构造相交链表
        for(int i = 0 ; i < 10 ; i += 2)
            ListHead1 = InsertListTail(ListHead1 , i);
        for(int i = 1 ; i < 5 ; i += 1)
            ListHead2 = InsertListTail(ListHead2 , i);
        for(int i = 2 ; i < 8 ; i += 3)
            ListHead3 = InsertListTail(ListHead3 , i);
        struct ListNode *TempNode = ListHead1;
        while(TempNode->pNext != NULL)//找到最后一个节点
            TempNode = TempNode->pNext;//等于下一个节点
        TempNode->pNext = ListHead3;
        TempNode = ListHead2;
        while(TempNode->pNext != NULL)//找到最后一个节点
            TempNode = TempNode->pNext;//等于下一个节点
        TempNode->pNext = ListHead3;
        printf("相交与：%d\n" , JudgeCrossListAnd(ListHead1 , ListHead2)->key);
    
        return 0;
    }

![这里写图片描述][Image 1]

## 10、删除单链表中重复的结点 ##

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5  
首先建立空节点，然后通过两个指针进行比较即可。

class Solution {
    public:
        /* 1、链表有序，所以可以遍历实现。然后就是仔细画图了，相当重要的。 */
        ListNode* deleteDuplication(ListNode* pHead)
        {
            if(pHead == NULL || pHead->next == NULL)//没有节点或者只有一个节点，则直接返回。
                return pHead;
            ListNode Head(0);//存储头节点，防止先前头结点重复了
            Head.next = pHead;
            ListNode *preNode = &Head;//最近没有重复的节点
            ListNode *curNode = pHead;//探寻重复的节点，前进
            while(curNode != NULL){
                if(curNode->next != NULL && curNode->val == curNode->next->val){
       //相等，curNode继续往后面寻找
                    while(curNode->next != NULL && curNode->val == curNode->next->val)//一直寻找,直到某个值不等
                        curNode = curNode->next;
                    preNode->next = curNode->next;//指向下一个节点
                    curNode = curNode->next;//指向下一个不等的节点
                }else{
       //不相等，则一起前进一步
                    preNode = preNode->next;//指向当前没有重复的节点
                    curNode = curNode->next;//指向下一个
                }
            }
            return Head.next;
        }
    };

hash\_map方法访问

## 11、以O(1)复杂度删除链表中节点 ##

![这里写图片描述][70 8]  
方法一：删除结点i之前 ， 先从链表的头给点开始边历到i前面的一个结点h，把h的pNext指向i的下一个结点再删除结点i。请注意特殊情况，详情见代码。  
方法二：把给点 j 的内容复制覆盖结点i，接下来再把结点i的m\_pNext指向j的下一个结点之后，删除结点j。这种方法不用遍历链表上结点i前面的结点。请注意特殊情况，详情见代码。  
以上的前提是节点在链表中，否则必须遍历确认，那么就没有实质性了。并且首先应该考虑的就是防御性编程，在接口开始验证传入参数的正确性。

/* 遍历删除,时间复杂度是O(n) 注意:删除头节点和删除后面节点不一样. */
    struct ListNode *DeleteNode_On(struct ListNode *pListHead , struct ListNode *pToBeDeleted)
    {
        //边界判断,防御性编程
        if(pListHead == NULL || pToBeDeleted == NULL)
            return pListHead;
        //1、如果删除头节点,则直接返回头节点
        if(pListHead == pToBeDeleted){
            pListHead = pToBeDeleted->pNext;//保存下个节点信息
            free(pToBeDeleted);//删除本节点
            return pListHead;//返回头节点
        }
        //2、如果删除不是头节点,则遍历即可
        struct ListNode *pNode = pListHead;
        while(pNode->pNext != pToBeDeleted)//删除后面节点,则找到要删除的节点的前一个节点
            pNode = pNode->pNext;
        pNode->pNext = pToBeDeleted->pNext;//前一个节点链接起来,并删除
        free(pToBeDeleted);
        return pListHead;
    }
    /* 找到删除节点下一个节点,时间复杂度是O(1) */
    struct ListNode *DeleteNode_O1(struct ListNode *pListHead , struct ListNode *pToBeDeleted)
    {
        struct ListNode *pNode = pListHead;
    
        //边界判断,防御性编程
        if(pListHead == NULL || pToBeDeleted == NULL)
            return pListHead;
    
        //1.如果删除头节点,则直接返回头节点
        if(pListHead == pToBeDeleted){
            pListHead = pToBeDeleted->pNext;//保存下个节点信息
            free(pToBeDeleted);//删除本节点
            return pListHead;//返回头节点
        }
        //2.如果删除的是尾部节点,则利用遍历删除
        if(pToBeDeleted->pNext == NULL){
            while(pNode->pNext != pToBeDeleted)//找到删除山一个节点
                pNode = pNode->pNext;
            pNode->pNext = pToBeDeleted->pNext;//前一个节点链接起来,并删除
            free(pToBeDeleted);
            return pListHead;
        }
    
        //3.如果删除节点是中间节点,那么利用O(1)算法
        pNode = pToBeDeleted->pNext;//删除节点下一个节点
             //下个节点拷贝给删除节点
        pToBeDeleted->key = pNode->key;
        pToBeDeleted->pNext = pNode->pNext;
        free(pNode);//删除下一个节点
        return pListHead;
    }

[70]: /images/20220530/07803bd227de4fe59dabc37482986270.png
[70 1]: /images/20220530/a9535e5cbeeb4fcea0ae0d512edba1c4.png
[70 2]: /images/20220530/dc4350f2a2f743ee82bd290af9e4b82a.png
[https_www.cnblogs.com_TenosDoIt_p_3666585.html]: https://www.cnblogs.com/TenosDoIt/p/3666585.html
[70 3]: /images/20220530/f76b140f1bc5469aa7a8edd9ea9d367b.png
[70 4]: /images/20220530/33fc1d868e6a4618931b3825393b4196.png
[Link 1]: https://www.cnblogs.com/xudong-bupt/p/3667729.html
[70 5]: /images/20220530/9c74e7d93beb4e7883f957080be39706.png
[70 6]: /images/20220530/6d3397855974445f9effa9c051cc17f6.png
[70 7]: /images/20220530/63a0982af7f34bcdaeb9bf0dbc72b642.png
[Image 1]: 
[70 8]: /images/20220530/684690f88dde4c8294e5142cb8f61570.png