【刷算法】兩種類型的刪除有序鏈表中的重復(fù)節(jié)點

googollee 發(fā)布于2019-08-22 18:07 / 1350人閱讀

摘要：題目描述刪除有序鏈表中的重復(fù)節(jié)點，返回頭節(jié)點刪除掉所有重復(fù)節(jié)點，例如，返回重復(fù)的節(jié)點中保留一個，例如，返回刪除掉所有重復(fù)節(jié)點細節(jié)這里面有幾個需要注意的細節(jié)新建一個空的頭節(jié)點，因為這里面牽扯到換新的鏈表頭的問題，所

題目描述

刪除有序鏈表中的重復(fù)節(jié)點，返回頭節(jié)點

刪除掉所有重復(fù)節(jié)點，例如1->1->2->2->3->4，返回3->4

重復(fù)的節(jié)點中保留一個，例如1->1->2->2->3->4，返回1->2->3->4

刪除掉所有重復(fù)節(jié)點

function ListNode(x){
    this.val = x;
    this.next = null;
}
function deleteDuplication(pHead){
    if(pHead === null || pHead.next === null) 
        return pHead;
    var H = new ListNode(null);
    H.next = pHead;

    var pre = H;
    var cur = pHead;

    while(cur !== null && cur.next !== null) {
        if(cur.next.val === cur.val){
            var curRepetitiveVal = cur.val;
            while(cur !== null && cur.val === curRepetitiveVal) {
                cur = cur.next;
            }
            pre.next = cur;
        }else{
            pre = cur;
            cur = cur.next;
        }
    }

    return H.next;
}

細節(jié)
這里面有幾個需要注意的細節(jié)：

新建一個空的頭節(jié)點，因為這里面牽扯到換新的鏈表頭的問題，所以為了方便新建一個新的節(jié)點作為鏈表的頭節(jié)點

每個重復(fù)節(jié)點中保留一個

function ListNode(x){
    this.val = x;
    this.next = null;
}
function deleteDuplication(pHead){
    if(pHead === null || pHead.next === null) 
        return pHead;
    var H = new ListNode(null);
    H.next = pHead;

    var pre = H;
    var cur = pHead;

    while(cur !== null && cur.next !== null) {
        if(cur.next.val === cur.val){
            pre = cur;
            var curRepetitiveVal = cur.val;
            while(cur !== null && cur.val === curRepetitiveVal) {
                cur = cur.next;
            }
            pre.next = cur;
        }else{
            pre = cur;
            cur = cur.next;
        }
    }    

    return H.next;
}

細節(jié)

這個和刪除掉所有重復(fù)節(jié)點的區(qū)別就是發(fā)現(xiàn)有相同的節(jié)點時，pre指針立馬指向重復(fù)的節(jié)點中的第一個節(jié)點