83. 删除排序链表中的重复元素

方法1

遍历链表，如果当前节点与下一个节点数据相同，则令当前节点的next指向当前节点的next->next

/** * 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 *p=head; if(p==NULL || p->next==NULL) return head; while(p->next!=NULL){ if(p->next!=NULL&&p->next->val==p->val){ p->next=p->next->next; } else if(p->next!=NULL&&p->next->val!=p->val){ p=p->next; } } return head; } };

执行用时 : 28 ms, 在Remove Duplicates from Sorted List的C++提交中击败了41.70% 的用户 内存消耗 : 9.4 MB, 在Remove Duplicates from Sorted List的C++提交中击败了5.97% 的用户

方法2

用空间换时间，创建新的链表，和之前的链表上的每个节点数据进行比较，不相同则创建新节点插入，相同则比较下一个。

/** * 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 || head->next==NULL) return head; ListNode *p=new ListNode(NULL),*result; result=p; p->next=new ListNode(head->val);p=p->next; ListNode *q=head->next; while(q!=NULL){ if(p->val!=q->val){ p->next=new ListNode(q->val); p=p->next; }else{ q=q->next; } } return result->next; } };

执行用时 : 16 ms, 在Remove Duplicates from Sorted List的C++提交中击败了97.78% 的用户 内存消耗 : 9.5 MB, 在Remove Duplicates from Sorted List的C++提交中击败了5.13% 的用户