链表相关面试题第三篇

灰太狼 2023-01-21 12:26 153阅读 0赞

![在这里插入图片描述][resize_m_lfit_w_962_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、环形链表
 *   *   *  1.题目描述
         *  2.解题思路
 *  二、环形链表进阶
 *   *   *  1.题目描述
         *  2.解题思路
 *  三、复杂带随机指针的链表
 *   *   *  1.题目描述
         *  2.解题思路
 *  四、对链表进行插入排序
 *   *   *  1.题目描述
         *  2.解题思路
 *  五、删除链表中重复节点，重复节点不保留
 *   *   *  1.题目描述
         *  2.解题思路
 *  总结

--------------------

# 前言 #

--------------------

![在这里插入图片描述][2021051610290570.png_pic_left]

# 一、环形链表 #

[环形链表][Link 1]

### 1.题目描述 ###

1.  给定一个链表，判断链表中是否有环。
2.  如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
3.  注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
    ![在这里插入图片描述][20210516103722123.png]

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
代码如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    bool hasCycle(struct ListNode *head)
    { 
        struct ListNode* fast=head,*slow=head;
        while(fast&&fast->next)
        { 
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow)
            { 
                return true;
            }
        }
        return false;
    }

# 二、环形链表进阶 #

[环形链表进阶][Link 2]

### 1.题目描述 ###

1.  给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。  
    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
2.  说明：不允许修改给定的链表。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]  
    ![在这里插入图片描述][20210516103839852.png]

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]  
代码如下：

struct ListNode *detectCycle(struct ListNode *head) 
    { 
        struct ListNode* fast=head,*slow=head;
        while(fast&&fast->next)
        { 
            fast=fast->next->next;
            slow=slow->next;
            if(slow==fast)
            { 
                struct ListNode* meet=fast;
                while(meet!=head)
                { 
                    meet=meet->next;
                    head=head->next;
                }
                return meet;
            }
        }
        return NULL;
    }

# 三、复杂带随机指针的链表 #

[复杂带随机指针的链表][Link 3]

### 1.题目描述 ###

1.  给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
2.  例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
3.  返回复制链表的头节点。
4.  用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 \[val, random\_index\] 表示：
5.  val：一个表示 Node.val 的整数。random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。你的代码只接受原链表的头节点 head 作为传入参数。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]  
    ![在这里插入图片描述][20210516104134426.png]

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 9]  
代码如下：

struct Node* copyRandomList(struct Node* head) 
    { 
        if(head==NULL)
        { 
            return NULL;
        }
        //1.拷贝节点挂在原节点的后面
    	struct Node* cur=head;
        while(cur)
        { 
            struct Node* next=cur->next;
            struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
            copy->val=cur->val;
            cur->next=copy;
            copy->next=next;
            cur=next;
        }
        //2.处理copy节点的random
        cur=head;
        while(cur)
        { 
            struct Node* copy=cur->next;
            if(cur->random==NULL)
            { 
                copy->random=NULL;
            }
            else
            { 
                copy->random=cur->random->next;
            }
            cur=copy->next;
        }
        //3.把拷贝的节点取下来链接到一起，恢复原链表
        cur=head;
        struct Node* copyHead,*copyTail;
        copyHead=copyTail=(struct Node*)malloc(sizeof(struct Node));
        while(cur)
        { 
            struct Node* copy=cur->next;
            struct Node* next=copy->next;
            //尾插
            copyTail->next=copy;
            copyTail=copyTail->next;
    
            cur->next=next;
            cur=next;
        }
        struct Node* guard=copyHead;
        copyHead=copyHead->next;
        free(guard);
        return copyHead;
    }

# 四、对链表进行插入排序 #

[对链表进行插入排序][Link 4]

### 1.题目描述 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 10]

1.  对链表进行插入排序。  
    插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。  
    每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
2.  插入排序算法：  
    插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。  
    每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。  
    重复直到所有输入数据插入完为止。

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 11]  
代码如下：

struct ListNode* insertionSortList(struct ListNode* head)
    { 
        if(head==NULL||head->next==NULL)
        { 
            return head;
        }
        //起始条件
        struct ListNode* sortHead=head;
        struct ListNode* cur=sortHead->next;
        sortHead->next=NULL;
        while(cur)  //终止条件cur为空
        { 
            struct ListNode* next=cur->next;
            struct ListNode* p=NULL;
            struct ListNode* c=sortHead;
            while(c)
            { 
                if(c->val>cur->val)
                { 
                    break;
                }
                else
                { 
                    p=c;
                    c=c->next;
                }
            }
            if(p==NULL)  //一个节点都没有
            { 
                cur->next=c;
                sortHead=cur; //cur来当头节点
            }
            else        //中间插入
            { 
                p->next=cur;
                cur->next=c;
            }
            cur=next;
        }
        return sortHead;
    }

# 五、删除链表中重复节点，重复节点不保留 #

[删除链表中重复节点，重复节点不保留][Link 5]

### 1.题目描述 ###

1.  在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 12]

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 13]  
代码如下：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */
    class Solution { 
    public:
        ListNode* deleteDuplication(ListNode* pHead) 
        { 
            if(pHead==NULL||pHead->next==NULL)
            { 
                return pHead;
            }
            struct ListNode* prev=NULL;
            struct ListNode* cur=pHead;
            struct ListNode* next=pHead->next;
            while(next)
            { 
               if(cur->val==next->val)
               {    
                  while(next && cur->val==next->val)
                  { 
                     next=next->next;
                  }
                  while(cur!=next)
                  { 
                      struct ListNode* del=cur;
                      cur=cur->next;
                      free(del);
                  }
                  if(prev==NULL)
                  { 
                      pHead=cur;
                  }
                  else
                  { 
                      prev->next=cur;
                  }
                  if(next)
                  { 
                      next=next->next;
                  }
               }
               else
               { 
                prev=cur;
                cur=next;
                next=next->next;
               }
            }
            return pHead;
        }
    };

--------------------

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了链表几道经典题的解法，会继续发布链表后面的题目解法，希望大家多多支持。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][resize_m_lfit_w_962_pic_center 1]

[resize_m_lfit_w_962_pic_center]: /images/20221020/1cba4ddc7765434c8a93e9bebbf196ac.png
[2021051610290570.png_pic_left]: /images/20221020/c91bb408e6e042b29e99edc234f5c878.png
[Link 1]: https://leetcode-cn.com/problems/linked-list-cycle/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221020/570a5b95a5b44733a470a2388d03c370.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221020/50eb800a4a374336808b0fc89681c541.png
[20210516103722123.png]: /images/20221020/d0a96220cd3d4490b86c935135980990.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221020/08e3c3007925494e9da4a8f07651db32.png
[Link 2]: https://leetcode-cn.com/problems/linked-list-cycle-ii/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221020/335f64c023f9464e8bf027a940379b89.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221020/36d52fca73cc4b6585900ea592a96ae2.png
[20210516103839852.png]: /images/20221020/bc362a2f7fdc4d49b70d523a420549ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221020/571d8690367c45c080ec5c9f2bfae237.png
[Link 3]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/description/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]: /images/20221020/41a9b34c3b654a79a18f482b6f55d233.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]: /images/20221020/b9746eb6bacb41c184d8a031b28d329d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 8]: /images/20221020/beb35a2bef6b4736bf0d0dd77bf3568c.png
[20210516104134426.png]: /images/20221020/465dd0f0d15e440c9918ff2ee41c6781.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 9]: /images/20221020/9a2c1b21dfa04d5bb9c6e65d1c53baab.png
[Link 4]: https://leetcode-cn.com/problems/insertion-sort-list/submissions/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 10]: /images/20221020/746143222ece4ef695a1bc84de0cc477.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 11]: /images/20221020/fb0827335a094ccc89cdde9bd8698842.png
[Link 5]: https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking&tab=answerKey
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 12]: /images/20221020/7b27cf591a44405eae28eb4d25f50b3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 13]: /images/20221020/15769417607e4031ba07b31f79c628e5.png
[resize_m_lfit_w_962_pic_center 1]: /images/20221020/0a3eb76d5c6a4f00ab24da84bb871272.png