Leetcode_14 天数据结构入门_day8

今天还是链表哦

206. Reverse Linked List

这个题做过啦，参考：Leetcode_14 天算法入门_day10
再写一遍~

83. Remove Duplicates from Sorted List

Analysis

删除有序链表的重复元素，既然给定的是有序的，那么重复元素一定是相邻的，这样就好办了。

Code

method 1

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return nullptr;
        ListNode *cur = head, *p;
        while(cur) {
            if(cur->next != nullptr && cur->val == cur->next->val) {
                p = cur->next;
                cur->next = p->next;
                delete(p);
            } else cur = cur->next;
        }
        return head;
    }
};

method 2

不用想，肯定有递归的做法😂。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
        head->next = deleteDuplicates(head->next);
        if(head->val == head->next->val) head->next = head->next->next;
        return head;
    }
};

递归是在回退的时候删除的结点，但本质上并没有将结点占用的内存手动释放掉。

Summary

链表的题做了一些了，基本思路算是齐活了，就是递归写的不熟练...

---