remove-duplicates-from-sorted-list I&II—

I、Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given1->1->2, return1->2.
Given1->1->2->3->3, return1->2->3.

PS：遍历，而后记录pre，并删除后续重复node

 /**

  * 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) {

         ListNode *cur=head,*pre=NULL;

         while(cur!=NULL){

             if(pre==NULL){

                 pre=cur;

                 cur=cur->next;

                 continue;

             }

             ListNode *next=cur->next;

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

                 pre->next=next;

             }else

                 pre=cur;

             cur=next;

         }

         return head;

     }

 };

II、

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

For example,
Given1->2->3->3->4->4->5, return1->2->5.
Given1->1->1->2->3, return2->3.

删除所有重复项。

PS：循环比较next->val==cur->val，若next跳动则剔除cur至next之间的节点。否则右移left指针。

 /**

  * 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 h(-);

         ListNode *res=&h;

         res->next=head;

         ListNode *cur=head,*pre=NULL,*left=res;

         while(cur!=NULL){

             ListNode* next=cur->next;

             while(next!=NULL&&cur->val==next->val){

                 next=next->next;

             }

             if(next==cur->next){

                 left=cur;

             }else{

                 left->next=next;

             }

             cur=next;

         }

         return res->next;

     }

 };

巴特西

remove-duplicates-from-sorted-list I&II——去除链表中重复项

最新文章

热门文章