我正在研究 Javascript 中的資料結構以準備面試，并且對解決方案中的回傳值感到有些困惑。詳情如下。
問題 （參考鏈接）：https ://www.hackerrank.com/challenges/delete-a-node-from-a-linked-list/problem
洗掉鏈表中給定位置的節點并回傳對頭節點的參考。頭在位置 0。洗掉節點后串列可能為空。在這種情況下，回傳一個空值。
樣板：
const SinglyLinkedListNode = class {
constructor(nodeData) {
this.data = nodeData;
this.next = null;
}
};
const SinglyLinkedList = class {
constructor() {
this.head = null;
this.tail = null;
}
insertNode(nodeData) {
const node = new SinglyLinkedListNode(nodeData);
if (this.head == null) {
this.head = node;
} else {
this.tail.next = node;
}
this.tail = node;
}
};
function printSinglyLinkedList(node, sep, ws) {
while (node != null) {
ws.write(String(node.data));
node = node.next;
if (node != null) {
ws.write(sep);
}
}
}
和功能的答案：
/*
* Complete the 'deleteNode' function below.
*
* The function is expected to return an INTEGER_SINGLY_LINKED_LIST.
* The function accepts following parameters:
* 1. INTEGER_SINGLY_LINKED_LIST llist
* 2. INTEGER position
*/
/*
* For your reference:
*
* SinglyLinkedListNode {
* int data;
* SinglyLinkedListNode next;
* }
*
*/
function deleteNode(llist, position) {
let head = llist
let currentNode = head
let count = 1
if (head === null) return;
if (position === 0){
head = head.next
return head
if (currentNode === null || currentNode.next === null) return;
while (count < position){
count
currentNode = currentNode.next
}
currentNode.next = currentNode.next.next
return head
}
此功能似乎通過了提供的所有測驗。
我的問題是：為什么回傳“頭”會給我正確的答案？似乎 head 在函式中沒有被改變。回傳 llist 也給出了正確的答案。
我試過回傳 currentNode 但顯然它提供了 currentNode 上的值。
uj5u.com熱心網友回復：
為什么回傳“頭”會給我正確的答案？
因為head是對節點的參考。只是因為該節點本身也具有對下一個節點的參考，并且該下一個節點也可能具有對下一個節點的參考，所以該head參考暗示了一個鏈表。即使head參考的節點可能保持相同的節點，沿著該next參考鏈的某處，可能會發生變化（并且將會發生變化），因此隱含地參考head導致不再相同的鏈表。
似乎 head 在函式中沒有被改變。
除非是頭節點本身需要被移除，否則這是一個正確的說法。那是因為head只參考第一個節點。所以如果第一個節點必須留在鏈表中，head不需要改變。將改變的是next沿途某處的參考。
回傳
llist也給出了正確的答案。
是的，變數的引入head實際上是矯枉過正。我們可以在沒有額外變數的情況下解決這個問題，只需llist在代碼使用的地方使用head.
這可能有助于形象化。
假設我們有一個有四個節點的鏈表（值為 1、2、3 和 4）并且position是 2。那么當代碼執行到while陳述句時，我們有這個狀態：
llist
head currentNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 1 │ │ value: 2 │ │ value: 3 │ │ value: 4 │
│ next: ───────> │ next: ───────> │ next: ───────> │ next:None │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
與position2 一樣，此代碼的目的是從該串列中洗掉值為 3 的節點。
在這種while情況下，回圈將進行一次迭代，因此currentNode將參考需要洗掉的節點的前任：
llist
head currentNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 1 │ │ value: 2 │ │ value: 3 │ │ value: 4 │
│ next: ───────> │ next: ───────> │ next: ───────> │ next:None │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
nextwhile 回圈之后的第一條陳述句對存盤在該前驅節點中的參考執行“重定向” ：
llist
head currentNode
↓ ↓ ┌────────────────┐
┌───────────┐ ┌───────────┐ │ ┌───────────┐ │ ┌───────────┐
│ value: 1 │ │ value: 2 │ │ │ value: 3 │ └> │ value: 4 │
│ next: ───────> │ next: ──────┘ │ next: ───────> │ next:None │
└───────────┘ └───────────┘ └───────────┘ └───────────┘
請注意，不再有任何內容參考值為 3 的節點。任何 JavaScript 代碼都無法訪問它。垃圾收集器可以釋放它的記憶體，所以上面和這個沒有什么不同：
llist
head currentNode
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│ value: 1 │ │ value: 2 │ │ value: 4 │
│ next: ───────> │ next: ───────> │ next:None │
└───────────┘ └───────────┘ └───────────┘
在這一切程序中，head并沒有改變。這種變化反映在next參考鏈中的一個節點上，因此我們可以說鏈表是mutated。
我希望這能闡明它是如何作業的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/506464.html
標籤：javascript 指针 数据结构 链表 逻辑
下一篇：從C 中的函式回傳一個陣列