牛客网刷题01——删除链表重复元素

https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?tpId=13&tqId=11209&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目:在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->5

解题思路:需要新建一个头指针指向原来链表的头结点,因为头结点有可能需要被删除。再设置两个指针,一个快指针一个慢指针,慢指针每次遍历都指向这轮的第一个元素,快指针指向重复元素的最后一个元素,当这轮结束后如果慢指针的下一个元素是快指针,即意味着慢指针和快指针之间没有重复元素,则慢指针指向快指针指向的元素,否则慢指针指向快指针指向的下一个元素。

/*  
 struct ListNode {  
 int val;  
 struct ListNode *next;  
 ListNode(int x) :  
 val(x), next(NULL) {  
 }  
 };  
 */  
 class Solution {  
 public:  
 ListNode* deleteDuplication(ListNode* pHead)  
 {  
 if(pHead==NULL || pHead->next==NULL) return pHead;  
 ListNode* newHead = new ListNode(0);  
 newHead->next = pHead;  
 ListNode* pre = newHead;  
 while (pre->next != NULL) {  
 ListNode* curr = pre->next;  
 while (curr->next != NULL && curr->next->val == curr->val) {  
 curr = curr->next;  
 }  
 if (pre->next != curr) {  
 pre->next = curr->next;  
 } else {  
 pre = pre->next;  
 }  
 }  
 return newHead->next;  
 }  
 };

comments powered by Disqus