第82题：删除排序链表中的重复元素II

一．问题描述

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

二．解题思路

本题思路：本题采用双指针的方法进行一次遍历得到答案。

步骤一：设置一个头指针first,first.next=head,设置另一个指针second指向head。

步骤二：判断second指针指向的数字与下一个是否相等，如果不等则添加到first指针后面，重复步骤二，如果相等进入步骤三。

步骤三：将当前second指针指向的数设成标记数，second指针指向下一个数字，遍历链表（步骤四）。

步骤四：当标记数等于second指针指向的数字，则继续进行遍历，跳过当前所有重复数字。跳过重复标记数后返回步骤二。

三．执行结果

四．执行用时 :1 ms, 在所有 java 提交中击败了99.29%的用户

五．内存消耗 :36.4 MB, 在所有 java 提交中击败了65.11%的用户

六． Java代码

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

          ListNode first=new ListNode(0);

          first.next=head;

          ListNode result=first;

          ListNode second=head;

          if(head==null)

          {

              return head;

          }

          while(second!=null) {

              if(second.next==null)

              {

                  first.next=second;

                  break;

              }

              if(second.val!=second.next.val)

              {

                  first.next=second;

                  first=second;

                  second=second.next;

                  continue;

              }

              int data=second.val;

              second=second.next;

              while(second!=null&&data==second.val)

              {

                  second=second.next;

                  if(second==null)

                  {

                      first.next=second;

                      break;

                  }

              }

          }

          return result.next;

    }

}

巴特西

第82题：删除排序链表中的重复元素II

最新文章

热门文章