精益求精解LeetCode(82与83)

2019 年 10 月 6 日
筆記

好久没有刷题与更文了，今天来一场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;  }

今日刷题完毕，好久没有刷题了，累了，休息，闪了，欢迎大家转发，收藏，点赞！