刷題前必學！鏈表實戰！用JavaScript學數據結構與算法詳情 - javascript,算法,數據結構,數據結構和算法,segmentfault HowieCong 動態日志

🧑‍💻JavaScript算法與數據結構-HowieCong

務必要熟悉JavaScript使用再來學！

一、鏈表三種方向

鏈表的處理：合併、刪除等（刪除操作畫個記號）
鏈表的反轉及其衍生題目
鏈表成環問題及其衍生題目

二、鏈表的合併

原題：

將兩個有序鏈表合併為一個新的有序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有結點組成的。

示例：

輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4

（1）思路分析

中心思想：處理鏈表的本質，是處理鏈表結點之間的指針關係

兩個鏈表如果想要合併為一個鏈表，我們恰當地補充雙方之間結點next指針地指向關係，就能達到目的
先比較一下眼前的兩個結點，選擇其中值較少的那個，優先把它串進去，一次串一個，直到所有結點被串起來，同時我們還要考慮l1和l2兩個鏈表長度不等的情況：若其中一個鏈表已經完全被串進新鏈表裏了，而另外一個鏈表還還有剩餘結點，考慮到該鏈表本身就是有序的，可以直接把它整個拼到目標鏈表的尾部

（2）編碼實現

const mergeTwoLists = function(l1,l2){
    // 定義頭結點，確保鏈表可以被訪問到
    let head = new ListNode()
    
    // cur 這裏就是咱們那根線
    let cur = head
    
    // 線開始在l1和l2間行走
    while(l1 && l2){
        // 如果l1的結點值較小
        if(l1.val <= l2.val){
            // 先串起 l1 的結點
            cur.next = l1
            // l1指針向前一步
            l1 = l1.next
        }else{
            // l2較小時，串起l2結點
            cur.next = l2
            l2 = l2.next
        }
        // 線在串起一個結點後，也會向前一步
        cur = cur.next
    }
    // 處理鏈表不等長的情況
    cur.next = l1 !== null ? l1:l2
    // 返回起始結點
    return head.next
}

三、鏈表結點的刪除

原題：

給定一個排序鏈表，刪除所有重複的元素，使得每個元素只出現一次

示例：

輸入: 1->1->2\
輸出: 1->2\
示例 2:\
輸入: 1->1->2->3->3\
輸出: 1->2->3

（1）思路分析

鏈表的刪除是一個基礎且關鍵的操作，這裏直接複用刪除能力，將需要刪除的目標結點的前驅結點next指針往後指一格

判斷兩個元素是否重複，由於此處是已排序的鏈表，我們直接判斷前後兩個元素值是否相等即可
考察了鏈表的遍歷，while循環，也考察了鏈表的CRUD的刪除操作

（2）編碼實現

const deleteDuplicates = function(head){
    // cur指針，初始位置為鏈表第一個結點
    let cur = head;
    // 遍歷鏈表
    while(cur != null && cur.next != null){
    // 若當前結點和它後面一個結點值相等（重複）
        if(cur.val === cur.next.val){
            // 刪除靠後的那個結點（去重）
            cur.next = cur.next.next;
        }else{
            // 若不重複，繼續遍歷
            cur = cur.next;
        }
    }
    return head;
}

四、刪除問題——dummy結點

原題：

給定一個排序鏈表，刪除所有含有重複數字的結點，只保留原始鏈表中沒有重複出現的數字

示例：

輸入: 1->2->3->3->4->4->5\
輸出: 1->2->5\
示例 2:\
輸入: 1->1->1->2->3\
輸出: 2->3

（1）思路分析

和上道題的區別在於，上題是刪到沒有重複元素就行，這個題要求只要一個元素髮生了重複，就要徹底從鏈表去掉
鏈表的第一個結點，沒有前驅節點，可以用一個dummy結點來解決這個問題
dummy結點就是自己去new的第一個結點的前驅節點，確保了鏈表的所有結點都有一個前驅結點，能幫助我們降低鏈表處理過程的複雜度
處理鏈表時，不設dummy結點思路可能會打不開，設了dummy結點，不用到，也不會出錯
定義一個dummy結點，指向鏈表的起始位置

如果想刪除兩個連續重複的值為1的結點，只需要把dummy結點的next指針直接指向2

由於重複的結點可能不止一個兩個，需要使用一個while循環來反覆進行重複結點的判斷和刪除判斷

（2）編碼實現

const deleteDuplicates = function(head){
    // 特殊：0個或1個結點，不會重複，直接返回
    if(!head || !head.next){
        return head
    }
    
    // dummy出現
    let dummy = new ListNode()
    // dummy永遠指向頭結點
    dummy.next = head
    // cur從dummy開始遍歷
    let cur = dummy
    // 當cur的後面有至少兩個結點時
    whilt(cur.next && cur.next.next){
        // 對cur的後面至少有兩個結點時
        if(cur.next.val === cur.next.next.val){
            // 若值重複，則記下這個值
            let val = cur.next.val
            // 反覆地排查後面的元素是否存在多次重複該值的情況
            while(cur.next && cur.next.val===val){
                // 若有，則刪除
                cur.next = cur.next.next
            }else{
                // 若不重複，則正常遍歷
                cur = cur.next
            }
        }
    }
    // 返回鏈表的起始結點
    return dummy.next;
}

❓其他

1. 疑問與作者HowieCong聲明

如有疑問、出錯的知識，請及時點擊下方鏈接添加作者HowieCong的其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
若想讓作者更新哪些方面的技術文章或補充更多知識在這篇文章，請及時點擊下方鏈接添加里面其中一種聯繫方式或發送郵件到下方郵箱告知作者HowieCong
聲明：作者HowieCong目前只是一個前端開發小菜鳥，寫文章的初衷只是全面提高自身能力和見識；如果對此篇文章喜歡或能幫助到你，麻煩給作者HowieCong點個關注/給這篇文章點個贊/收藏這篇文章/在評論區留下你的想法吧，歡迎大家來交流！