數據結構之“鏈表”

• 鏈表是什么？
• 數組 vs 鏈表
• JS中的鏈表
• LeetCode：237.刪除鏈表中的節點
• LeetCode：206.反轉鏈表
• LeetCode：2.兩數相加
• LeetCode：83.刪除排序鏈表中的重復元素
• LeetCode：141.環形鏈表
• 前端與鏈表（JS中的原型鏈）
• • 一、instanceof的使用，并用代碼實現
• 二
• 前端鏈表：使用鏈表指針獲取JSON的節點值
• 總結
• 思考題

鏈表是什么？

多個元素組成的列表
元素存儲不連續，用next指針連在一起

數組 vs 鏈表

數組：增刪非首尾元素是往往需要移動元素
鏈表：增刪非首尾元素，不需要移動元素，只需要更改next的指向即可

JS中的鏈表

JavaScript中沒有鏈表
可以用Object模擬鏈表

const a = { val: 'a' }; const b = { val: 'b' }; const c = { val: 'c' }; const d = { val: 'd' }; a.next = b; b.next = c; c.next = d;// 遍歷鏈表 let p = a; while (p) {console.log(p.val);p = p.next; }// 插入 const e = { val: 'e' }; c.next = e; e.next = d;// 刪除 c.next = d;

LeetCode：237.刪除鏈表中的節點

解題思路
無法直接獲取被刪除節點的上個節點
將被刪除節點轉移到下個節點
解題步驟
將被刪節點的值改為下個節點的值
刪除下個節點

時間復雜度O(1)，空間復雜度O(1)

LeetCode：206.反轉鏈表

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

解題思路
反轉兩個節點：將n + 1的next指向n
反轉多個節點：雙指針遍歷鏈表，重復上述操作

解題步驟
雙指針一前一后遍歷鏈表
反轉雙指針

時間復雜度O(n)，空間復雜度O(1)

LeetCode：2.兩數相加

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

解題思路
小學數學題，模擬相加操作
需要遍歷鏈表

解題步驟
新建一個空鏈表
遍歷被相加的兩個鏈表，模擬相加操作，將個位數追加到新鏈表上，將十位數留到下一位去相加

時間復雜度O(n)，空間復雜度O(n)

LeetCode：83.刪除排序鏈表中的重復元素

輸入：1 -> 1 -> 2
輸出：1 -> 2

解題思路
因為鏈表是有序的，所以重復元素一定相鄰
遍歷鏈表，如果發現當前元素和下個元素值相同，就刪除下個元素值

解題步驟
遍歷鏈表，如果發現當前元素和下個元素值相同，就刪除下個元素值
遍歷結束后，返回原鏈表的頭部

時間復雜度O(n)，空間復雜度O(1)

LeetCode：141.環形鏈表

解題思路
兩個人在圓形操場上的起點同時起跑，速度快的人一定會超過速度慢的人一圈
用一快一慢兩個指針遍歷鏈表，如果指針能夠相逢，那么鏈表就有圈

解題步驟
用一快一慢兩個指針遍歷鏈表，如果指針能夠相逢，就返回true
遍歷結束后，還沒有相逢就返回false

時間復雜度O(n)，空間復雜度O(1)

前端與鏈表（JS中的原型鏈）

原型鏈簡介
原型鏈的本質是鏈表
原型鏈上的節點是各種原型對象，比如Function.prototype、Object.prototype…
原型鏈通過__proto__屬性鏈接各種原型對象
原型鏈長啥樣
obj -> Object.prototype -> null
func -> Function.prototype -> Object.prototype -> null
arr -> Array.prototype -> Object.prototype -> null
原型鏈知識點
如果A沿著原型鏈能找到B的原型對象（B.prototype），那么A instanceof B為true
如果在A對象上沒有找到x屬性，那么會沿著原型鏈找x屬性

const obj = {} const func = () => {} const arr = [] //原型鏈通過__proto__屬性鏈接各種原型對象 console.log(obj .__proto__ === Object.prototype) //true console.log(func.__proto__ === Function.prototype) //true console.log(func.__proto__.__proto__ === Object.prototype) //true console.log(arr.__proto__ === Array.prototype) //true console.log(arr.__proto__.__proto__ === Object.prototype) //true//如果A沿著原型鏈能找到B的原型對象（B.prototype），那么A instanceof B為true console.log(func instanceof Function) //true console.log(func instanceof Object) //true //fuc的proto屬性指向Function的原型對象， //func即是object的實例，也是function的實例//如果在A對象上沒有找到x屬性，那么會沿著原型鏈找x屬性 const obj = {}; Object.prototype.x = 'x' const func = () => {}; Function.prototype.y = 'y' console.log(obj.x) //x console.log(obj.y) //undefined console.log(func.x) //x console.log(func.y) //y

一、instanceof的使用，并用代碼實現

分析
知識點：如果A沿著原型鏈能找到B.prototype，那么A instanceof B為true
解法：遍歷A的原型鏈，如果找到B.prototype，返回true，否則返回false

const instanceOf = (A,B) => {let p = A;while (p) {if (p === B.prototype) {return true;}p = p.__proto__;}return false; }

二

var foo = {},F = Function(){}; Object.prototype.a = 'value a'; Function.prototype.b = 'value b'console.log(foo.a) console.log(foo.b)console.log(F.a) console.log(F.b)

分析
知識點：如果在A對象上沒有找到x屬性，那么會沿著原型鏈找x屬性
解法：明確foo和F變量的原型鏈，沿著原型鏈找a屬性和b屬性

前端鏈表：使用鏈表指針獲取JSON的節點值

const json = {a: { b: { c: 1 } },d: { e: 2 }, } const path = ['a', 'b' ,'c'] let p =json; path.forEach(k => {p = p[k]; })

總結

鏈表里的元素存儲不是連續的，之間通過next連接
JavaScript中沒有鏈表，但可以用Object模擬鏈表
鏈表常用操作：修改next、遍歷鏈表
JS中的原型鏈也是一個鏈表
使用鏈表指針可以獲取JSON的節點值

思考題

1、編寫一個 instanceOf 方法，可以判斷一個變量是否是另一個變量的實例
2、請判斷一個鏈表是否為回文鏈表。題目鏈接：https://leetcode-cn.com/problems/palindrome-linked-list/

總結

以上是生活随笔為你收集整理的（五）数据结构之“链表”的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。