被火车撞了都不能忘记的几道题（你会了吗？）

目录

一.删除有序链表中的重复元素I

二.删除有序链表重复元素II

三.环形单链表中插入一个元素

四.单链表翻转II

五.奇偶链表

---

一.删除有序链表中的重复元素I

1.对应牛客网链接：

删除有序链表中重复的元素-I_牛客题霸_牛客网 (nowcoder.com)

2.题目描述：

 3.解题思路

1.定义一个cur和next指针一开始cur指向头，next指针指向头的下一个

2.边遍历边比较 cur->val == next->val，若相等，则将 cur 就指向 next 的下一个节点，否则继续遍历，直至遍历完整个链表。

下面以1->2->3->3->4为例：

由于 cur 指向的节点的值（1）不等于 next 指向的节点的值（2），两个指针右移

不相等继续后移

相等，cur 指向 next 的下一节点（相当于删除链表中的重复元素 3），next 指针右移

直到next为空

4.对应代码

   

    

     

      

     
     

      

       class 
       Solution {
      
     
    

     

      

     
     

      
  
       public:
      
     
    

     

      

     
     

      
    
       /**
      
     
    

     

      

     
     

      

        *
      
     
    

     

      

     
     

      

        * @param head ListNode类
      
     
    

     

      

     
     

      

        * @return ListNode类
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
    
       ListNode* deleteDuplicates(ListNode* head) {
      
     
    

     

      

     
     

      
        
       // write code here
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
        
       if (head == 
       nullptr || head->next == 
       nullptr) {
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

               ListNode* cur = head;
      
     
    

     

      

     
     

      

               ListNode* next = head->next;
      
     
    

     

      

     
     

      
        
       while (next) {
      
     
    

     

      

     
     

      
            
       if (cur->val == next->val) { 
       //重复
      
     
    

     

      

     
     

      
                
       while (next && next->val == next->val) {
      
     
    

     

      

     
     

      

                           ListNode* next = cur->next; 
       //保存下一个节点
      
     
    

     

      

     
     

      
                    
       delete cur;
      
     
    

     

      

     
     

      

                           cur = next;
      
     
    

     

      

     
     

      

                       }
      
     
    

     

      

     
     

      

                       cur->next = next;
      
     
    

     

      

     
     

      

                   } 
       else {
      
     
    

     

      

     
     

      
                
       //指针一起移动
      
     
    

     

      

     
     

      

                       cur = next;
      
     
    

     

      

     
     

      

                       next = next->next;
      
     
    

     

      

     
     

      

                   }
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      
        
       return head;
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       };
      
     
   

递归版本：

   

    

     

      

     
     

      

       class 
       Solution {
      
     
    

     

      

     
     

      
  
       public:
      
     
    

     

      

     
     

      
    
       /**
      
     
    

     

      

     
     

      

        *
      
     
    

     

      

     
     

      

        * @param head ListNode类
      
     
    

     

      

     
     

      

        * @return ListNode类
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
    
       ListNode* deleteDuplicates(ListNode* head) {
      
     
    

     

      

     
     

      
        
       // write code here
      
     
    

     

      

     
     

      
        
       if (!head || !head->next) {
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

               ListNode* next = head->next;
      
     
    

     

      

     
     

      
        
       if (head->val != next->val) {
      
     
    

     

      

     
     

      

                   head->next = 
       deleteDuplicates(head->next);
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               } 
       else {
      
     
    

     

      

     
     

      
            
       while (next && next->val == head->val) {
      
     
    

     

      

     
     

      

                       head->next = next->next;
      
     
    

     

      

     
     

      
                
       delete next;
      
     
    

     

      

     
     

      

                       next = head->next;
      
     
    

     

      

     
     

      

                   }
      
     
    

     

      

     
     

      

                   head->next = 
       deleteDuplicates(head->next);
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       };
      
     
   

二.删除有序链表重复元素II

1.对应牛客网链接：

删除有序链表中重复的元素-II_牛客题霸_牛客网 (nowcoder.com)

2.题目描述：

 3.解题思路

1.定义一个三个指针变量：last 、prev、cur一开始分别指针空、头节点和头节点的下一个

2.迭代变量如果prev的值和cur的值相等那么一直移动cur直到cur的值和prev不相等。如果prev的值和cur不相等则三个指针一起移动。直到cur为空

下面我们以1->3->3->4->4->5为例：

初始状态：

 发现prev和cur的值不相等三个指针一起移动

 此时prev和cur的值一样我们进行删除：

删除完成之后我们发现prev和cur的值又相等了继续进行删除

直到cur走到空结束循环将头节点返回即可

注意：（如果一开始就是头删需要进行特判改变头节点） 

4.对应代码

   

    

     

      

     
     

      

       class 
       Solution {
      
     
    

     

      

     
     

      
  
       public:
      
     
    

     

      

     
     

      
    
       /**
      
     
    

     

      

     
     

      

        *
      
     
    

     

      

     
     

      

        * @param head ListNode类
      
     
    

     

      

     
     

      

        * @return ListNode类
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
    
       ListNode* deleteDuplicates(ListNode* head) {
      
     
    

     

      

     
     

      
        
       // write code here
      
     
    

     

      

     
     

      
        
       if (head == 
       nullptr || head->next == 
       nullptr) {
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

               ListNode* prev = head;
      
     
    

     

      

     
     

      

               ListNode* cur = head->next;
      
     
    

     

      

     
     

      

               ListNode* last = 
       nullptr;
      
     
    

     

      

     
     

      
        
       while (cur) {
      
     
    

     

      

     
     

      
            
       if (cur->val == prev->val) {
      
     
    

     

      

     
     

      
                
       while (cur && cur->val == prev->val) {
       //进行删除
      
     
    

     

      

     
     

      

                           ListNode* next = cur->next;
      
     
    

     

      

     
     

      
                    
       delete cur;
      
     
    

     

      

     
     

      

                           cur = next;
      
     
    

     

      

     
     

      

                       }
      
     
    

     

      

     
     

      
                
       delete prev;
      
     
    

     

      

     
     

      

                       prev = cur;
      
     
    

     

      

     
     

      

                       cur = cur ? cur->next : 
       nullptr;
      
     
    

     

      

     
     

      
                
       if (last == 
       nullptr) {
       //特判头删的情况
      
     
    

     

      

     
     

      

                           head = prev;
      
     
    

     

      

     
     

      

                       } 
       else {
      
     
    

     

      

     
     

      

                           last->next = prev;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

                       }
      
     
    

     

      

     
     

      

                   } 
       else {
       //三个指针迭代走
      
     
    

     

      

     
     

      

                       last = prev;
      
     
    

     

      

     
     

      

                       prev = cur;
      
     
    

     

      

     
     

      

                       cur = cur->next;
      
     
    

     

      

     
     

      

                   }
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      
        
       return head;
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       };
      
     
   

递归版本：

   

    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       class 
       Solution {
      
     
    

     

      

     
     

      
  
       public:
      
     
    

     

      

     
     

      
    
       /**
      
     
    

     

      

     
     

      

        *
      
     
    

     

      

     
     

      

        * @param head ListNode类
      
     
    

     

      

     
     

      

        * @return ListNode类
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
    
       ListNode* deleteDuplicates(ListNode* head) {
      
     
    

     

      

     
     

      
        
       // write code here
      
     
    

     

      

     
     

      
        
       if (head == 
       nullptr || head->next == 
       nullptr) {
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      
        
       if (head->val != head->next->val) {
      
     
    

     

      

     
     

      

                   head->next = 
       deleteDuplicates(head->next);
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               } 
       else {
      
     
    

     

      

     
     

      
            
       //说明相等
      
     
    

     

      

     
     

      
            
       int val = head->val;
      
     
    

     

      

     
     

      
            
       while (val == head->val) {
      
     
    

     

      

     
     

      

                       ListNode* next = head->next;
      
     
    

     

      

     
     

      
                
       delete head;
      
     
    

     

      

     
     

      

                       head = next;
      
     
    

     

      

     
     

      
                
       if (head == 
       nullptr)
      
     
    

     

      

     
     

      
                    
       return 
       nullptr;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

                   }
      
     
    

     

      

     
     

      
            
       return 
       deleteDuplicates(head);
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       };
      
     
   

三.环形单链表中插入一个元素

1.对应letecode链接：

剑指 Offer II 029. 排序的循环链表 - 力扣（LeetCode）

2.题目描述：

3.解题思路：

 插入情况一：链表为空创建一个节点让自己指向自己

插入情况二：单链表只有一个节点或单链表中所有节点的值都相等

插入情况三：找到一个插入位置使其前节点值比Insertval小，后节点值比其Insertval大

情况四：当插入节点为最小值或者最大值

4.对应代码：

   

    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       class 
       Solution {
      
     
    

     

      

     
     

      
  
       public:
      
     
    

     

      

     
     

      
    
       Node* insert(Node* head, int insertVal) {
      
     
    

     

      

     
     

      
        
       if (head == 
       NULL) {
      
     
    

     

      

     
     

      

                   Node* newNode = 
       new 
       Node(insertVal);
      
     
    

     

      

     
     

      

                   newNode->next = newNode;
      
     
    

     

      

     
     

      
            
       return newNode;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

               Node* cur = head;
      
     
    

     

      

     
     

      
        
       while (
       1) {
      
     
    

     

      

     
     

      
            
       if (cur->next ==
      
     
    

     

      

     
     

      

                           head) { 
       //说明可能只有一个节点或者全是一种值的节点
      
     
    

     

      

     
     

      
                
       break;
      
     
    

     

      

     
     

      

                   } 
       else 
       if (cur->val <= insertVal && cur->next->val >= insertVal) {
      
     
    

     

      

     
     

      
                
       break;
      
     
    

     

      

     
     

      

                   } 
       else 
       if (cur->val > cur->next->val && (insertVal >= cur->val ||
      
     
    

     

      

     
     

      

                              insertVal <= cur->next->val)) {
      
     
    

     

      

     
     

      
                
       break;
      
     
    

     

      

     
     

      

                   }
      
     
    

     

      

     
     

      

                   cur = cur->next;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

               cur->next = 
       new 
       Node(insertVal, cur->next);
      
     
    

     

      

     
     

      
        
       return head;
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       };
      
     
   

四.单链表翻转II

1.对应牛客网链接

链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)

2.题目描述：

3.解题思路：

1.指向 left左边元素的指针 pre ，它表示未翻转的链表，需要把当前要翻转的链表结点放到 pre 之后。

cur 指向当前要翻转的链表结点。

nxt 指向 cur.next ，表示下一个要被翻转的链表结点。

tail 指向已经翻转的链表的结尾，用它来把已翻转的链表和剩余链表进行拼接

 

 4.对应代码：

   

    

     

      

     
     

      

       /**
      
     
    

     

      

     
     

      

        * struct ListNode {
      
     
    

     

      

     
     

      

        * int val;
      
     
    

     

      

     
     

      

        * struct ListNode *next;
      
     
    

     

      

     
     

      

        * };
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       class 
       Solution {
      
     
    

     

      

     
     

      

       public:
      
     
    

     

      

     
     

      
    
       /**
      
     
    

     

      

     
     

      

        * 
      
     
    

     

      

     
     

      

        * @param head ListNode类 
      
     
    

     

      

     
     

      

        * @param m int整型 
      
     
    

     

      

     
     

      

        * @param n int整型 
      
     
    

     

      

     
     

      

        * @return ListNode类
      
     
    

     

      

     
     

      

        */
      
     
    

     

      

     
     

      

           ListNode*temp=
       nullptr;
      
     
    

     

      

     
     

      
    
       ListNode* reverseBetween(ListNode* head, int m, int n) {
      
     
    

     

      

     
     

      
        
       // write code here
      
     
    

     

      

     
     

      
        
       if(m==
       1)
      
     
    

     

      

     
     

      

               {
      
     
    

     

      

     
     

      
            
       return 
       ReversN(head, n);
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

               ListNode*node=
       reverseBetween(head->next, m
       -1, n
       -1);
      
     
    

     

      

     
     

      

               head->next=node;
      
     
    

     

      

     
     

      
        
       return head;
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      
    
       ListNode*ReversN(ListNode*head,int n)
      
     
    

     

      

     
     

      

           {
      
     
    

     

      

     
     

      
        
       if(n==
       1)
      
     
    

     

      

     
     

      

               {
      
     
    

     

      

     
     

      

                   temp=head->next;
       //保存后面的节点
      
     
    

     

      

     
     

      
            
       return head;
      
     
    

     

      

     
     

      

               }
      
     
    

     

      

     
     

      

               ListNode*node=
       ReversN(head->next,n
       -1);
      
     
    

     

      

     
     

      
        
       //开始翻转
      
     
    

     

      

     
     

      

               head->next->next=head;
      
     
    

     

      

     
     

      

               head->next=temp;
      
     
    

     

      

     
     

      
        
       return node;
      
     
    

     

      

     
     

      
        
      
     
    

     

      

     
     

      

           }
      
     
    

     

      

     
     

      

       };
      
     
   

递归版本：

1.如果m ==1,就相当于反转链表的前n元素。
2.如果m != 1我们把 head的索引视为1，那么我们是想从第m个元素开始反转，如果扎head.next的索引视为1，那相对于head.next，反转的区间3.应该是从第m-1个元素始的，以此类推，递归拼接后续已反转的链表。
对于每次反转，如果n等于1，相当于只颠倒第一个节点，如果不是，则进入后续节点问题)，将后续反转的内容接到前面即可。