問題描述

在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針。 例如，鏈表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)
    {   
        // 將沒有重復的節(jié)點存入對列中
        Queue<ListNode> queue = initQueue(pHead);
        return getResultHead(queue);
    }
    
    public ListNode getResultHead(Queue<ListNode> queue){
        // 遍歷隊列 構造新的結果鏈表 將頭節(jié)點返回
        ListNode newHead = null;
        ListNode tail = null;
        while(!queue.isEmpty()){
            // 頭節(jié)點為空 初始化頭節(jié)點 記錄鏈表頭節(jié)點
            if(newHead == null){
                newHead = queue.poll();
                tail = newHead;
                tail.next = null;
                continue;
            }
            // 剩下的節(jié)點連接到頭節(jié)點的后面
            tail.next = queue.poll();
            tail = tail.next;
            tail.next = null;
        }
        return newHead;
    }
    
    public Queue initQueue(ListNode pHead){
       /**使用雙端隊列 存儲鏈表節(jié)點，如果使用棧，則結果序列順序與元鏈表節(jié)點順序不一樣，
          使用雙端隊列可以使用棧的特性，并保持結果序列與與換來鏈表序列順序一樣
       */
       Deque<ListNode> queue = new LinkedList<ListNode>();
        if(pHead == null){
            return queue;
        }
        queue.addLast(pHead);
        pHead = pHead.next;
        while(pHead != null){
            // 標識當前節(jié)點是否重復 如果重復則要從雙端隊列中移除
            boolean flag = false;
            int peekValue = queue.peekLast().val;
            // 比較雙端隊列隊尾節(jié)點的val與當前節(jié)點val是否相同，相同就后移，并標志該隊尾節(jié)點要出隊
            while(null != pHead && pHead.val == peekValue){
                pHead = pHead.next;
                flag = true;
            }
            // 如果為重復的節(jié)點，則出隊
            if(flag){
                queue.pollLast();
            }
            // 防止隊尾空節(jié)點入隊
            if(null != pHead){
                queue.addLast(pHead);
                pHead = pHead.next; 
            }
        }
        return queue;
    }
}

方法二
借助輔助頭結點，可避免單獨討論頭結點的情況。設置兩個結點 pre 和 cur，當 cur 和 cur.next 值相等，cur 一直向前走，直到不等退出循環(huán)，這時候 cur 指的值還是重復值，調整 cur 和 pre 的指針再次判斷

public class Solution {
     public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null || pHead.next == null){
            return pHead;
        }
        // 自己構建輔助頭結點
        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){
                // 相同結點一直前進
                while(cur.next != null && cur.next.val == cur.val){
                    cur = cur.next;
                }
                // 退出循環(huán)時，cur 指向重復值，也需要刪除，而 cur.next 指向第一個不重復的值
                // cur 繼續(xù)前進
                cur = cur.next;
                // pre 連接新結點
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }
}