問題描述

在一個(gè)排序的鏈表中撤师，存在重復(fù)的結(jié)點(diǎn)绵脯，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)，重復(fù)的結(jié)點(diǎn)不保留跨新，返回鏈表頭指針富腊。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5

解題思路

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {   
        // 將沒有重復(fù)的節(jié)點(diǎn)存入對(duì)列中
        Queue<ListNode> queue = initQueue(pHead);
        return getResultHead(queue);
    }
    
    public ListNode getResultHead(Queue<ListNode> queue){
        // 遍歷隊(duì)列 構(gòu)造新的結(jié)果鏈表 將頭節(jié)點(diǎn)返回
        ListNode newHead = null;
        ListNode tail = null;
        while(!queue.isEmpty()){
            // 頭節(jié)點(diǎn)為空 初始化頭節(jié)點(diǎn) 記錄鏈表頭節(jié)點(diǎn)
            if(newHead == null){
                newHead = queue.poll();
                tail = newHead;
                tail.next = null;
                continue;
            }
            // 剩下的節(jié)點(diǎn)連接到頭節(jié)點(diǎn)的后面
            tail.next = queue.poll();
            tail = tail.next;
            tail.next = null;
        }
        return newHead;
    }
    
    public Queue initQueue(ListNode pHead){
       /**使用雙端隊(duì)列 存儲(chǔ)鏈表節(jié)點(diǎn)域帐，如果使用棧赘被，則結(jié)果序列順序與元鏈表節(jié)點(diǎn)順序不一樣是整，
          使用雙端隊(duì)列可以使用棧的特性，并保持結(jié)果序列與與換來鏈表序列順序一樣
       */
       Deque<ListNode> queue = new LinkedList<ListNode>();
        if(pHead == null){
            return queue;
        }
        queue.addLast(pHead);
        pHead = pHead.next;
        while(pHead != null){
            // 標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)是否重復(fù) 如果重復(fù)則要從雙端隊(duì)列中移除
            boolean flag = false;
            int peekValue = queue.peekLast().val;
            // 比較雙端隊(duì)列隊(duì)尾節(jié)點(diǎn)的val與當(dāng)前節(jié)點(diǎn)val是否相同民假，相同就后移浮入，并標(biāo)志該隊(duì)尾節(jié)點(diǎn)要出隊(duì)
            while(null != pHead && pHead.val == peekValue){
                pHead = pHead.next;
                flag = true;
            }
            // 如果為重復(fù)的節(jié)點(diǎn)，則出隊(duì)
            if(flag){
                queue.pollLast();
            }
            // 防止隊(duì)尾空節(jié)點(diǎn)入隊(duì)
            if(null != pHead){
                queue.addLast(pHead);
                pHead = pHead.next; 
            }
        }
        return queue;
    }
}

方法二
借助輔助頭結(jié)點(diǎn)羊异，可避免單獨(dú)討論頭結(jié)點(diǎn)的情況事秀。設(shè)置兩個(gè)結(jié)點(diǎn) pre 和 cur，當(dāng) cur 和 cur.next 值相等野舶，cur 一直向前走易迹，直到不等退出循環(huán)，這時(shí)候 cur 指的值還是重復(fù)值平道，調(diào)整 cur 和 pre 的指針再次判斷

public class Solution {
     public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null || pHead.next == null){
            return pHead;
        }
        // 自己構(gòu)建輔助頭結(jié)點(diǎn)
        ListNode head = new ListNode(Integer.MIN_VALUE);
        head.next = pHead;
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.next != null && cur.next.val == cur.val){
                // 相同結(jié)點(diǎn)一直前進(jìn)
                while(cur.next != null && cur.next.val == cur.val){
                    cur = cur.next;
                }
                // 退出循環(huán)時(shí)睹欲，cur 指向重復(fù)值，也需要?jiǎng)h除巢掺，而 cur.next 指向第一個(gè)不重復(fù)的值
                // cur 繼續(xù)前進(jìn)
                cur = cur.next;
                // pre 連接新結(jié)點(diǎn)
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }
}