精益求精解LeetCode(82与83)
精益求精解LeetCode(82与83)
好久没有刷题与更文了，今天来一场LeetCode上面简单与中等题目多种方法刷题。
1.题目
83. 删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2输出: 1->2示例 2:
输入: 1->1->2->3->3输出: 1->2->3
2.思想
（1）使用快慢指针
特殊情况判断：链表为空或链表只有一个节点，直接返回。
设p=head，q=head->next，让不断去移动，直到q的val不等于p的val，那么将p连接上q即可。
循环特殊情况判断，当快指针指向为空，直接让p指向NULL，break掉函数，返回即可。
分析：时间复杂度为O(n)，空间复杂度为O(1)。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head==NULL||head->next==NULL) return head;
ListNode *p=head,*q=p->next;
while(p) {
if(p->val!=q->val) {
p->next=q;
p=q;
}
q=q->next;
if(q==NULL){
p->next=NULL;
break;
}
}
return head;
}
};（2）递归
递归终止条件：无节点或只有一个节点。
递归到最后，例如尾部节点为2 2，也就是当head->next指向末尾的2时候，此时需要判断head与head->next值是否相等，如果相等，直接让head指向尾部，依次覆盖所有重复节点。否则，直接让head指向尾部节点。
分析：时间复杂度为O(n)，空间复杂度为O(1)。
ListNode* deleteDuplicates(ListNode* head) {
//链表是否为空或者是否到末尾
if (head == NULL || head->next == NULL)
return head;
ListNode *p = deleteDuplicates(head->next);
if (head->val == head->next->val)
head = p;
else
head->next = p;
return head;
}2.题目
82. 删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5输出: 1->2->5示例 2:
输入: 1->1->1->2->3输出: 2->3
3.思想
3.1方法一
这道题与上述题目很相似，于是采用上述题目思想完成。
上述思想中核心就是快慢指针，快指针q，满指针p，每次q指向的是新元素，也就是满足p->val!=q->val,就需要判断当前链表是否值不同连续。
值不同连续判断就是p->next==q,(两者距离只差1)。如果满足,说明当前p指向的元素无重复,那么直接让r(此指针为新返回链表的遍历指针)指针指向p指向的节点(注意这里是创建了一个p->val相同的节点)，r指针再指向下一个节点，q指针处理是不作为循环的遍历指针,每次++。
到最后,q指针为空,分为两种情况：
（1）值不同不连续: 例如：[1,2,2] p指向了2,q指向了NULL,此时需要将r->next指针直接指向末尾的NULL*
（2）值不同连续: 例如：[1,2,2,5] p指向了5,q指向了NULL,此时需要连接p,即r->next=p
ListNode* deleteDuplicates(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode* p=head,*q=p->next;
ListNode* HEAD=new ListNode(0),*r=HEAD;
while(q) {
cout<<p->val<<" "<<q->val<<endl;
if(p->val!=q->val) {
if(p->next==q) {
r->next=new ListNode(p->val);
r=r->next;
}
p=q;
}
cout<<r->val<<endl;
q=q->next;
}
if(p->next!=q)
r->next=NULL;
else
r->next=new ListNode(p->val);
r=HEAD->next;
delete HEAD;
return r;
}分析：*时间复杂度:O(n)，空间复杂度:O(n)。
那能否优化空间复杂度为O(1)呢？
我们继续优化。
3.2方法二
上述的空间复杂度耗费在每次都要去创建新的节点，那么我们不创建不就行了，只需要拓展一个指针，让该指针不断动态修改链表。
ListNode* deleteDuplicates(ListNode* head) {
// 无节点或者只有一个节点情况
if(head==NULL || head->next==NULL) return head;
// p跳跃指向不同节点,q遍历所有节点,r动态修改链表
ListNode* p=head,*q=p->next,*r=p;
// 针对 [1 1 2] 这种情况需要先确定返回链表头结点,那么这里创建一个头结点,让上述定义的r指针取动态的修改返回链表。
ListNode* HEAD=new ListNode(0); // 返回链表的头指针
while(q) {
/**
* 值不同
*/
if(p->val!=q->val) {
/**
* 值不同且连续
*/
if(p->next==q) {
/**
* 返回链表是否有开始节点
*/
if (HEAD->next == NULL) {
r = p;
HEAD->next = r;
} else {
r->next = p;
r = p;
}
}
// p指向新值
p=q;
}
q=q->next; //遍历链表
}
if(p->next!=q)
r->next=NULL;
else {
if(HEAD->next==NULL)
HEAD->next=p;
else
r->next=p;
}
r=HEAD->next;
delete HEAD;
return r;
}到最后,q指针为空,分为两种情况：
（1）值不同不连续
例如：[1,2,2] p指向了2,q指向了NULL,此时需要将r->next指针直接指向末尾的NULL
（2）值不同连续
- 值不同连续,且返回链表的没有开始节点，也就是HEAD->next=NULL 例如：[1,1,2] p指向了2,q指向了NULL，此时需要连接p,但是Head->next为空,直接让HEAD->next指向p即可
- 值不同连续,且回链表的有开始节。 例如：[1,2,2,5] p指向了5,q指向了NULL,此时需要连接p,即r->next=p
分析：时间复杂度：O(n)，空间复杂度O(1)。
到此为止，自己实现的思路全部写完，后面是看题解与评论上的一些思路，并对他们的代码做了一些优化后呈现出来的。
3.3 方法三
第82题用到了递归法，这道题也可以！
思想就是如果当前节点与后一节点相同，那么递归后一节点，直到找到不同的节点，并让前一节点(对应前面提到的当前节点)指向后一节点，依次递归下去，如果递归过程中当前节点与后一节点不同，直接链接，最后的head就是最终结果。
ListNode* deleteDuplicates2(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
ListNode *p = head->next;
if(head->val == p->val) {
while (p&&head->val==p->val){
p=p->next;
}
head=deleteDuplicates2(p);
} else {
head->next=deleteDuplicates2(p);
}
return head;
}时间复杂度O(n)，空间复杂度O(1)。
3.4 方法四
这个方法比较传统，在题解中空间复杂度为O(n)，这里我将其进行优化，最终的时间复杂度为O(n)，空间复杂度为O(1)。
思想是使用快慢指针，用慢指针跳过那些重复数，慢指针指的的元素就是返回链表中的元素。
ListNode* deleteDuplicates3(ListNode* head) {
if(head==NULL || head->next==NULL) return head;
// 1 1 2 2 3
ListNode *p=head,*q=p->next,*pre=head;
// 确定返回节点的头在哪里！
bool isonce=true;
while(p) {
if(q&&p->val==q->val) {
int tmp = p->val;
while(p&&p->val==tmp)
p=p->next;
if(p) q=p->next;
} else {
// 1 2 3 1 1 2 3
if (isonce) {
head = p;
isonce = false;
pre = head;
} else{
pre->next = p;
pre = p;
}
p=q;
if(q)
q=q->next;
}
}
if(isonce) {
head=NULL;
isonce=false;
} else {
pre->next=p;
}
return head;
}今日刷题完毕，好久没有刷题了，累了，休息，闪了，欢迎大家转发，收藏，点赞！