美文网首页
Leetcode-82:删除排序链表中的重复元素 II

Leetcode-82:删除排序链表中的重复元素 II

作者: 小北觅 | 来源:发表于2019-01-03 08:26 被阅读0次

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

    示例 1:

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

    示例 2:

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

    思路:

     h -> 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
    pre   cur
    

    我们始终要让 pre 在 cur 的前面,通过判断 cur.val == cur.next.val判断重复元素是否存在。

     h -> 1 -> 2    3    3    4 -> 4 -> 5
               |              |
               ----------------
              pre            cur
    

    如果存在重复元素的话,我们pre.next=cur.next;cur=cur.next,如果不存在重复元素,我们pre=cur;cur=cur.next,所以这里我们要通过一个变量标记是否存在重复元素。

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            
            if(head==null || head.next==null){
                return head;
            }  
            ListNode dummyHead = new ListNode(0);
            dummyHead.next = head;
            
            ListNode pre = dummyHead;
            ListNode cur = dummyHead.next;
            
            while(cur!=null){
                boolean isdup = false;
                while(cur.next!=null && cur.val == cur.next.val){
                    isdup = true;
                    cur=cur.next;
                }
                
                if(isdup){
                    cur = cur.next;
                    pre.next = cur;
                }else{
                    pre = cur;
                    cur = cur.next;
                }
                
            }
            return dummyHead.next;
        }
    }
    

    参考:Leetcode 82:删除排序链表中的重复元素 II(最详细解决方案!!!)

    相关文章

      网友评论

          本文标题:Leetcode-82:删除排序链表中的重复元素 II

          本文链接:https://www.haomeiwen.com/subject/esvxrqtx.html