leetcode83

一. 和leetcode82题思路一样,分为递归和非递归.

二. 递归写法.

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; //递归写法,和82题思路一样. class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head == NULL || head->next == NULL) return head; if (head != NULL&& head->next != NULL && head->val == head->next->val) { while (head != NULL&& head->next != NULL && head->val == head->next->val) { head = head->next; } //改动在这里,因为要保留一个重复的元素. head = deleteDuplicates(head); } else { head->next = deleteDuplicates(head->next); } return head; } }; class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head==NULL || head->next==NULL) return head; if(head->val==head->next->val) { while(head!=NULL && head->next!=NULL && head->val==head->next->val) head = head->next; head = deleteDuplicates(head); } else head->next = deleteDuplicates(head->next); return head; } };

三.  非递归写法

//非递归,借鉴递归的思路. class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* slow = dummy; ListNode* fast = head; while (fast != NULL) { if (fast->next != NULL&&fast->val == fast->next->val) { while (fast != NULL&&fast->next != NULL&&fast->val == fast->next->val) { fast = fast->next; } } else { slow->next = fast;; slow = fast; fast = fast->next; } } return dummy->next; } };

四.  最后附上大佬的思想, 递归套路解决链表问题：1.  找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return. 2.  想想应该返回什么值：应该返回的自然是已经去重的链表的头节点 3.  每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head.

作者：gpe3DBjDS1 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/solution/shan-chu-pai-xu-lian-biao-zhong-de-zhong-fu-yuan-2/