LeetCode(82)题解: Remove Duplicates from Sorted List II

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

题目：

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.

思路：

需要两个指针，a用来纪录新链表，b用来遍历老链表，因为只有删除操作，需要一个flag标记ab段要不要删除。此外要注意头节点的处理。

AC代码：

 /**

  * Definition for singly-linked list.

  * struct ListNode {

  *     int val;

  *     ListNode *next;

  *     ListNode(int x) : val(x), next(NULL) {}

  * };

  */

 class Solution {

 public:

     ListNode* deleteDuplicates(ListNode* head) {

         if(head==NULL)

             return NULL;

         ListNode* newhead=new ListNode();  // to handle head

         newhead->next=head;

         ListNode* a=newhead,*b=newhead->next;

         int now=head->val;

         bool occur_flag=false;

         while(b->next!=NULL){

             if(b->next->val==now){

                 occur_flag=true;

             }

             else{

                 if(occur_flag==true){

                     a->next=b->next;  //delete duplicate numbers

                     b=a;    //update pointers

                 }

                 else{

                     a=b;

                 }

                 occur_flag=false;

                 now=b->next->val;

             }

             b=b->next;

         }

         if(occur_flag==true){

             a->next=b->next;  //delete duplicate numbers

             b=a;    //update pointers

         }

         else{

             a=b;

         }

         return newhead->next;

     }

 };

巴特西

LeetCode(82)题解: Remove Duplicates from Sorted List II

最新文章

热门文章