每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（LinkedList）

妤鋒シ發(fā)布于2019-08-23 17:04 / 3524人閱讀

摘要：不同鏈表是鏈?zhǔn)降拇鎯Y(jié)構(gòu)數(shù)組是順序的存儲結(jié)構(gòu)。從列表中，移除并返回特定位置的一項。返回列表中元素個數(shù)，與數(shù)組的屬性類似。提示端優(yōu)先使用以上的語法實現(xiàn)。不要忘記在最后返回新的頭引用復(fù)雜度分析時間復(fù)雜度。假設(shè)是列表的長度，時間復(fù)雜度是。

這是第三周的練習(xí)題，原本應(yīng)該先發(fā)第二周的，因為周末的時候，我的母親大人來看望她的寶貝兒子，哈哈，我得帶她看看廈門這座美麗的城市呀。

這兩天我抓緊整理下第二周的題目和答案，下面我把之前的也列出來：

1.每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Stack）

歡迎關(guān)注我的 個人主頁 &&  個人博客 && 個人知識庫 && 微信公眾號“前端自習(xí)課”

本周練習(xí)內(nèi)容：數(shù)據(jù)結(jié)構(gòu)與算法 —— LinkedList

這些都是數(shù)據(jù)結(jié)構(gòu)與算法，一部分方法是團隊其他成員實現(xiàn)的，一部分我自己做的，有什么其他實現(xiàn)方法或錯誤，歡迎各位大佬指點，感謝。

一、鏈表是什么？與數(shù)組有什么區(qū)別？生活中有什么案例？

解析：
概念參考閱讀鏈表 —— 維基百科

1.概念：

鏈表（Linked list）是一種上一個元素的引用指向下一個元素的存儲結(jié)構(gòu)，鏈表通過指針來連接元素與元素；

鏈表是線性表的一種，所謂的線性表包含順序線性表和鏈表，順序線性表是用數(shù)組實現(xiàn)的，在內(nèi)存中有順序排列，通過改變數(shù)組大小實現(xiàn)。而鏈表不是用順序?qū)崿F(xiàn)的，用指針實現(xiàn)，在內(nèi)存中不連續(xù)。意思就是說，鏈表就是將一系列不連續(xù)的內(nèi)存聯(lián)系起來，將那種碎片內(nèi)存進行合理的利用，解決空間的問題。

所以，鏈表允許插入和刪除表上任意位置上的節(jié)點，但是不允許隨即存取。鏈表有很多種不同的類型：單向鏈表、雙向鏈表及循環(huán)鏈表。

2.與數(shù)組的區(qū)別：

相同：

兩種結(jié)構(gòu)均可實現(xiàn)數(shù)據(jù)的順序存儲，構(gòu)造出來的模型呈線性結(jié)構(gòu)。

不同：

鏈表是鏈?zhǔn)降拇鎯Y(jié)構(gòu)；數(shù)組是順序的存儲結(jié)構(gòu)。
鏈表通過指針來連接元素與元素，數(shù)組則是把所有元素按次序依次存儲。

鏈表的插入刪除元素相對數(shù)組較為簡單，不需要移動元素，且較為容易實現(xiàn)長度擴充，但是尋找某個元素較為困難。

數(shù)組尋找某個元素較為簡單，但插入與刪除比較復(fù)雜，由于最大長度需要再編程一開始時指定，故當(dāng)達到最大長度時，擴充長度不如鏈表方便。

數(shù)組和鏈表一些操作的時間復(fù)雜度對比：
數(shù)組：

查找復(fù)雜度：O(1)

添加/刪除復(fù)雜度：O(n)

鏈表：

查找復(fù)雜度：O(n)

添加/刪除復(fù)雜度：O(1)

3.生活中的案例：
火車，是由一些列車廂連接起來；
尋寶游戲，每個線索都是下一個線索地點的指針。

二、請事先一個鏈表，并實現(xiàn)以下方法

append(element)：向列表尾部添加一個新的元素。

insert(position, element)：向列表指定位置插入一個新的元素。

remove(element)：從列表中移除并返回特定元素（若有多個相同元素則取第一次出現(xiàn)的情況）。

indexOf(element)：返回元素在列表的索引（若有多個相同元素則取第一次出現(xiàn)的情況），如果列表中沒有該元素則返回 -1。

removeAt(position)：從列表中，移除并返回特定位置的一項。

isEmpty()：如果列表不含任何元素，返回 true，否則返回 false。

size()：返回列表中元素個數(shù)，與數(shù)組的 length 屬性類似。

toString()：由于列表項使用 Node 類，需要重寫繼承自 JavaScript 對象默認的 toString() 方法，讓其只輸出元素的值。

提示：Web 端優(yōu)先使用 ES6 以上的語法實現(xiàn)。

解析：

class Node {
    constructor(element){
        this.element = element
        this.next = null
    }
}
class LinkedList {
    constructor(){
        this.length = 0
        this.head = null
    }
    /**
     * 添加元素（末尾添加）
     * @param {*} element 添加的元素
     */
    append(element){
        let node = new Node(element)
        if(!this.head){
            this.head = node
        }else{
            let current = this.head
            // 查找最后一項
            while(current.next){
                current = current.next
            }
            // 將最后一下的next賦值為node，實現(xiàn)追加元素
            current.next = node
        }
        this.length ++
    }
    /**
     * 添加元素（指定位置）
     * @param {Number} position 添加的位置
     * @param {*} element  添加的元素
     */
    insert(position, element){
        if(position >= 0 && position <= this.length){
            let node = new Node(element),
                index = 0,
                previous = null
            if(position === 0){
                node.next = this.head
                this.head = node
            }else{
                let current = this.head
                while(index++ < position){
                    previous = current
                    current = current.next
                }
                previous.next = node
                node.next = current
            }
            this.length ++
        }
    }
    /**
     * 刪除元素
     * @param {*} element 刪除的元素
     * @return {*}  被刪除的元素
     */
    remove(element){
        let current = this.head,
            previous = null
        if(element === this.head.element){
            this.head = current.next
        }else{
            while(current.next && current.element !== element){
                previous = current
                current = current.next
            }
            previous.next = current.next
            this.length --
            return current.element
        }
    }
    /**
     * 刪除元素（指定位置）
     * @param {Number} position 刪除元素的位置
     * @return {*}  被刪除的元素
     */
    removeAt(position){
        if(position >= 0 && position <= this.length){
            let current = this.head,
                index = 0,
                previous = null
            if(position === 0){ // 刪除第一項
                this.head = current.next
            }else{
                while(index++ < position){
                    previous = current
                    current = current.next
                }
                previous.next = current.next
            }
            this.length --
            return current.element
        }
    }
    /**
     * 查找指定元素的位置
     * @param {*} element 查找的元素
     * @return {Number} 查找的元素的下標(biāo)
     */
    indexOf(element){
        let current = this.head, 
            index = 0
        while(current.next && current.element !== element){
            current = current.next
            index ++
        }
        return index === 0 ? -1 : index
    }
    /**
     * 鏈表是否為空
     * @return {Boolean}
     */
    isEmpty(){
        return this.length === 0
    }
    /**
     * 鏈表的長度
     * @return {Number}
     */
    size(){
        return this.length
    }
    /**
     * 將鏈表轉(zhuǎn)成字符串
     * @return {String}
     */
    toString(){
        let current = this.head,
            arr = new Array()
        while(current.next){
            arr.push(current.element)
            current = current.next
        }
        arr.push(current.element)
        return arr.toString()
    }
}

let leo = new LinkedList()
leo.append(3)
leo.append(6)
leo.append(9)
console.log(leo.length)
console.log(leo.head)
leo.remove(6)
console.log(leo.length)
console.log(leo.head)
console.log(leo.toString())

三、實現(xiàn)反轉(zhuǎn)鏈表

用鏈表的方式，輸出一個反轉(zhuǎn)后的單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
// input
let head = {
    "val": 1,"next": {
        "val": 2,"next": {
            "val": 3,"next": {
                "val": 4,"next": {
                    "val": 5,
                    "next": null
                }
            }
        }
    }
};
reverseList(head)

// output
head = {
    "val": 5,"next": {
        "val": 4,"next": {
            "val": 3,"next": {
                "val": 2,"next": {
                    "val": 1,
                    "next": null
                }
            }
        }
    }
};

解題思路1.使用迭代：
在遍歷列表時，將當(dāng)前節(jié)點的 next 指針改為指向前一個元素。由于節(jié)點沒有引用其上一個節(jié)點，因此必須先存儲其前一個元素。在更改引用之前，還需要另一個指針來存儲下一個節(jié)點。不要忘記在最后返回新的頭引用！

解題思路2.使用遞歸：
通過遞歸修改 head.next.next 和 head.next 指針來實現(xiàn)。

解析：
題目出自：Leetcode 206. 反轉(zhuǎn)鏈表

介紹兩種常用方法：

1.使用迭代：
在遍歷列表時，將當(dāng)前節(jié)點的 next 指針改為指向前一個元素。由于節(jié)點沒有引用其上一個節(jié)點，因此必須先存儲其前一個元素。在更改引用之前，還需要另一個指針來存儲下一個節(jié)點。不要忘記在最后返回新的頭引用！

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let reverseList = function(head) {
    let pre = null, curr = head
    while (curr) {
        next = curr.next
        curr.next = pre
        pre = curr
        curr = next
    }
    return pre
};

復(fù)雜度分析

時間復(fù)雜度：O(n)。假設(shè) n 是列表的長度，時間復(fù)雜度是 O(n)。
空間復(fù)雜度：O(1)。

2.使用遞歸：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let reverseList = function(head) {
    if(head == null || head.next == null) return head
    let pre = reverseList(head.next)
    head.next.next = head
    head.next = null
    return pre
};

復(fù)雜度分析

時間復(fù)雜度：O(n)。假設(shè) n 是列表的長度，那么時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(n)。由于使用遞歸，將會使用隱式?？臻g。遞歸深度可能會達到 n 層。

四、判斷鏈表是否有環(huán)

設(shè)計一個函數(shù) hasCycle，接收一個鏈表作為參數(shù)，判斷鏈表中是否有環(huán)。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果 pos 是 -1，則在該鏈表中沒有環(huán)。

需要注意的是，不可能存在多個環(huán)，最多只有一個。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第二個節(jié)點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環(huán)，其尾部連接到第一個節(jié)點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。

解題思路1.判斷是否有 null：
一直遍歷下去，如果遍歷到 null 則表示沒有環(huán)，否則有環(huán)，但是考慮到性能問題，最好給定一段時間作為限制，超過時間就不要繼續(xù)遍歷。

解題思路2.標(biāo)記法：
也是要遍歷每個節(jié)點，并在遍歷的節(jié)點添加標(biāo)記，如果后面遍歷過程中，遇到有這個標(biāo)記的節(jié)點，即表示有環(huán)，反之沒有環(huán)。

解題思路3.使用雙指針（龜兔賽跑式）：
設(shè)置2個指針，一個 快指針 每次走 2 步，慢指針 每次走 1 步，如果沒有環(huán)的情況，最后這兩個指針不會相遇，如果有環(huán)，會相遇。

解析：
題目出自：Leetcode 141. 環(huán)形鏈表

1.斷是否有 null

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
let hasCycle = function(head) {
    while(head){
        if(head.value == null) return true
        head.value = null
        head = head.next
    }
    return false
}

2.標(biāo)記法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
let hasCycle = function(head) {
    let node = head
    while(node){
        if(node.isVisit){
            return true
        }else{
            node.isVisit = true
        }
        node = node.next
    }
    return false
};

3.使用雙指針

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
let hasCycle = function(head) {
    if(head == null || head.next == null) return false
    let slow = head, fast = head.next
    while(slow != fast){
        if(fast == null || fast.next == null) return false
        slow = slow.next  // 慢指針每次走1步
        fast = fast.next.next // 快指針每次走1補
    }
    return true
};

五、實現(xiàn)兩兩交換鏈表中的節(jié)點

給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進行節(jié)點交換。

示例:

給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
給定 1->2->3->4->5, 你應(yīng)該返回 2->1->4->3->5.

解題思路1.使用迭代：
和反轉(zhuǎn)鏈表類似，關(guān)鍵在于有三個指針，分別指向前后和當(dāng)前節(jié)點，而不同在于兩兩交換后，移動節(jié)點的步長為2，需要注意。

解題思路2.使用遞歸：
這里也可以使用遞歸，也可以參考反轉(zhuǎn)鏈表的問題，終止條件是遞歸到鏈表為空，或者只剩下一個元素沒得交換了，才終止。

解析：
題目出自：Leetcode 24. 兩兩交換鏈表中的節(jié)點

介紹兩種常用方法：

1.使用迭代：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
let swapPairs = function (head){
    if(!head) return null
    let arr = []
    while(head){
        let next = head.next
        head.next = null
        arr.push(head)
        head = next
    }

    for(let i = 0; i < arr.length; i += 2){
        let [a, b] = [arr[i], arr[i + 1]]
        if(!b) continue
        [arr[i], arr[i + 1]] = [b, a]
    }

    for(let i = 0; i < arr.length - 1; i ++){
        arr[i].next = arr[i + 1]
    }
    return arr[0]
}

2.使用遞歸：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */

let swapPairs = function (head){
    if(head == null || head.next ==null) return head
    let next = head.next
    head.next = swapPairs(next.next)
    next.next = head
    return next
}

云服務(wù)器 GPU云服務(wù)器 webrtc之vad算法算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法看動畫學(xué)算法之:hashtable

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/103761.html

發(fā)表評論

登陸后可評論

0條評論

妤鋒シ

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow架構(gòu)

閱讀 3034·2023-04-25 18:06
《C語言入門》三子棋C語言實現(xiàn)（詳細版）

閱讀 3289·2021-11-22 09:34
GreenCloudVPS：新加坡機房全線4.4折優(yōu)惠，1G和10Gbps帶寬，KVM VPS年付$

閱讀 2863·2021-08-12 13:30
前端面試每日3+1——第116天

閱讀 2049·2019-08-30 15:44
第六天移動端Web開發(fā)注意事項

閱讀 1666·2019-08-30 13:09
Week3：張士超，你到底把一周的好文章放哪里了

閱讀 1634·2019-08-30 12:45
img的間隙

閱讀 1720·2019-08-29 11:13
面向Web設(shè)計和開發(fā)的12款Chrome插件

閱讀 3614·2019-08-28 17:51

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（LinkedList）

相關(guān)文章

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Queue）

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Set）

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Dictionary 和 HashTable）

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Dictionary 和 HashTable）

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（Tree）

發(fā)表評論

0條評論

妤鋒シ

男|高級講師

TA的文章

tensorflow架構(gòu)

《C語言入門》三子棋C語言實現(xiàn)（詳細版）

GreenCloudVPS：新加坡機房全線4.4折優(yōu)惠，1G和10Gbps帶寬，KVM VPS年付$

前端面試每日3+1——第116天

第六天移動端Web開發(fā)注意事項

Week3：張士超，你到底把一周的好文章放哪里了

img的間隙

面向Web設(shè)計和開發(fā)的12款Chrome插件

最新活動

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法（LinkedList）

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

每周一練之數(shù)據(jù)結(jié)構(gòu)與算法（LinkedList）