章節連結
鏈結串列(Linked List)本身在記憶體的儲存位置中並不是連續的，而是由各個節點(node)組成。每個 node 會有 item / next 兩個部分，由 next 的部份來進行串聯。因此，要進行同尾的刪除、新增，只需要加 next 的部份指向新的 node 即可。不過在運用時，要記得從 head 的部份來依序尋找，才能找到正確的位置來進行操作。
指令
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
/*Linked List*/ function LinkedList(){ let length = 0 let head = null let Node = function(element){ this.element = element this.next = null } this.append = (element)=>{ let node = new Node(element) let current = '' if(head === null){ head = node }else{ current = head while(current.next){ current = current.next } current.next = node } length++ } this.removeAt = (position)=>{ if(position>-1 && position<length){ let current = head let previous = '' let index = 0 if(position === 0){ head = current.next }else{ while(index++ < position){ previous = current current = current.next } } length-- return current.element }else{ return null } } this.insert = (position,element)=>{ if(position>-1 && position<length){ let node = new Node(element) let current = head let previous = '' let index = 0 if(position === 0){ node.next = current head = node }else{ while(index++ < position){ previous = current current = current.next } node.next = current previous.next = node } length++ return true }else{ return false } } this.toString = ()=>{ let current = head let string = '' while(current){ string += current.element current = current.next } return string } this.indexOf = (element)=>{ let current = head let index = 0 while(current){ if(element === current.element){ return index } index++ current = current.next } return -1 } this.remove = (element)=>{ let index = this.indexOf(element) return this.removeAt(index) } this.isEmpty = ()=>{ return length === 0 } this.size = ()=>{ return length } this.getHead = ()=>{ return head } } let list = new LinkedList() list.append(15) list.append(10) console.log(list.toString()) // 1510 list.append(12) list.append(18) list.insert(1,20) console.log(list.toString()) //1520101218 list.remove(18) console.log(list.isEmpty()) //false console.log(list.size()) console.log(list.indexOf(12)) //3 console.log(list.getHead()) // Node{element:15, next:{......}} |
LeetCode 練習記錄
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// 83. Remove Duplicates from Sorted List /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { // 當head為空 或是 head.next指向空值，直接回傳 head if( head === null || head.next === null ) return head // 將 head 的記憶體位置綁定到 ite 上 let ite = head // 當 ite.next 不是 null，將 ite.next 的值和 ite 本身的值比較 // 若是相同，則將 ite.next.next 的記憶體位置存入 ite.next // 否則，ite.next = ite while ( ite.next !== null ){ if( ite.val === ite.next.val ){ ite.next = ite.next.next }else{ ite = ite.next } } // 最後將 head 整個回傳即可 return head }; |
