leetcode 82. Remove Duplicates from Sorted List II

Dear 丶 2022-06-08 02:14 144阅读 0赞

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,  
Given 1->2->3->3->4->4->5, return 1->2->5.  
Given 1->1->1->2->3, return 2->3.

这道题很简答，遇到这种指针操作的题，最重要的就是细心。

代码如下：

/* class ListNode
     {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
     }*/
    
    public class Solution 
    {
        public ListNode deleteDuplicates(ListNode head) 
        {
            if(head==null || head.next==null)
                return head;
    
            ListNode finalListNode=new ListNode(0);
            ListNode resIter=finalListNode;
            ListNode iter=head;
            while(iter!=null)
            {
                ListNode fa=iter;
                ListNode son=iter.next;         
                //son为null表示列表走到尽头
                //fa的value和son的value第一次就不等，表示fa可以直接加入res列表
                if(son==null|| fa.val!=son.val)
                {
                    resIter.next=fa;
                    resIter=resIter.next;
                    resIter.next=null;  
                }else
                {
                    while(son!=null && fa.val==son.val)
                    {
                        fa=son;
                        son=son.next;
                    }
                }
                iter=son;
            }
            return finalListNode.next;
    
        }
    }

下面是C++的做法，

代码如下：

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    /*
    struct ListNode
    {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        ListNode* deleteDuplicates(ListNode* h) 
        {
            if (h == NULL || h->next == NULL)
                return h;
    
            ListNode* head = new ListNode(h->val - 2);
            head->next = h;
            ListNode* i = head;
    
            while (i != NULL)
            {
                ListNode* fa = i->next;
                ListNode* son = fa==NULL?NULL:fa->next;
                if (son==NULL || fa->val != son->val)
                    i = i->next;
                else
                {
                    ListNode* j = fa;
                    while (j != NULL && j->val == fa->val)
                        j = j->next;
                    i->next = j;
                }
            }
            return head->next;
        }
    };