Leetcode_14 天数据结构入门_day8

今天还是链表哦

206. Reverse Linked List

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

83. Remove Duplicates from Sorted List

Analysis

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

Code

method 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

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

1
2
3
4
5
6
7
8
9
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

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


Buy me a coffee ? :)
0%