iT邦幫忙

2

用 Javascript 操作 Linked List 的問題(LeetCode 206. Reverse Linked List)

  • 分享至 

  • xImage

近幾天為了測試自己自學的成果,所以上 LeetCode 練習解題。原以為自己在前面的題目已經基本熟悉了 Linked List 的操作,但是到了這題卻又出現意想不到的錯誤。

先附上程式碼:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  let nextNode = head.next;
  let currNode = head;
  let prevNode = null;
  while (true) {
    currNode.next = prevNode;
    currNode = nextNode;
    nextNode = nextNode.next;
    prevNode = currNode;
    if (!nextNode) { return currNode }
  }
};

錯誤訊息:

Line 13 in solution.js
  let nextNode = head.next;
                      ^
TypeError: Cannot read properties of null (reading 'next')
    Line 13: Char 23 in solution.js (reverseList)
    Line 33: Char 19 in solution.js (Object.<anonymous>)
    Line 16: Char 8 in runner.js (Object.runner)
    Line 24: Char 26 in solution.js (Object.<anonymous>)
    at Module._compile (node:internal/modules/cjs/loader:1101:14)
    at Object.Module._extensions..js (node:internal/modules/cjs/loader:1153:10)
    at Module.load (node:internal/modules/cjs/loader:981:32)
    at Function.Module._load (node:internal/modules/cjs/loader:822:12)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:81:12)
    at node:internal/main/run_main_module:17:47

head 明明是 list 的頭,為什麼不能接 .next

先前還嘗試過另一種寫法:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  let currNode = head;
  let prevNode; // 這裡很奇怪
  while (true) {
    const fixedCurrNode = currNode;
    currNode = currNode.next;
    fixedCurrNode.next = prevNode;
    prevNode = fixedCurrNode;
    if (!currNode) { return fixedCurrNode }
  }
};

如果 prevNode 最開始沒有賦值(undefined),就會報以下型別錯誤:

Line 37 in solution.js
             throw new TypeError(__serialize__(ret) + " is not valid value for the expected return type ListNode");
             ^
TypeError: {"val":5,"next":{"val":4,"next":{"val":3,"next":{"val":2,"next":{"val":1,"next":undefined}}}}} is not valid value for the expected return type ListNode
    Line 37: Char 20 in solution.js (Object.<anonymous>)
    Line 16: Char 8 in runner.js (Object.runner)
    Line 23: Char 26 in solution.js (Object.<anonymous>)
    at Module._compile (node:internal/modules/cjs/loader:1101:14)
    at Object.Module._extensions..js (node:internal/modules/cjs/loader:1153:10)
    at Module.load (node:internal/modules/cjs/loader:981:32)
    at Function.Module._load (node:internal/modules/cjs/loader:822:12)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:81:12)
    at node:internal/main/run_main_module:17:47

但如果在開始時就設 prevNode = null,就會跳出跟第一種寫法相似的錯誤:

Line 17 in solution.js
    currNode = currNode.next;
                        ^
TypeError: Cannot read properties of null (reading 'next')
    Line 17: Char 25 in solution.js (reverseList)
    Line 32: Char 19 in solution.js (Object.<anonymous>)
    Line 16: Char 8 in runner.js (Object.runner)
    Line 23: Char 26 in solution.js (Object.<anonymous>)
    at Module._compile (node:internal/modules/cjs/loader:1101:14)
    at Object.Module._extensions..js (node:internal/modules/cjs/loader:1153:10)
    at Module.load (node:internal/modules/cjs/loader:981:32)
    at Function.Module._load (node:internal/modules/cjs/loader:822:12)
    at Function.executeUserEntryPoint [as runMain] (node:internal/modules/run_main:81:12)
    at node:internal/main/run_main_module:17:47

我去 Solution 區看了一些別人寫的範例,看起來都跟我大同小異,但是卻沒有這種錯誤,在 Google 上也都只搜尋到誤當成 Array 操作的案例,請問各位前輩能不能指點一下修正的方向?

菜雞 iT邦新手 5 級 ‧ 2023-03-06 13:46:04 檢舉
好像找到問題了:忽略了 `head = []` 的情況,好笨……
Aoi iT邦新手 5 級 ‧ 2023-03-07 13:22:45 檢舉
根據您的程式碼,有幾個問題需要修正。

首先,在第一個程式碼片段中,您將 `head.next` 分配給 `nextNode`,這在頭節點是唯一節點時會導致錯誤,因為 `head.next` 會是 `null`。如果 `head` 是唯一節點,那麼 `nextNode` 會是 `null`,所以當您嘗試存取 `nextNode.next` 時會出現錯誤。因此,您需要在使用 `nextNode` 之前檢查它是否存在。

其次,在第二個程式碼片段中,初始值 `prevNode` 應該是 `null`,而不是未定義的。否則,在第一個迭代中,您嘗試將值分配給 `prevNode`,這將導致 `prevNode` 變成未定義的,而不是 `null`。這會導致在第二次迭代時出現錯誤,因為您嘗試將值分配給 `prevNode.next`,而 `prevNode` 未定義。

以下是經過修正的程式碼:javascript

var reverseList = function(head) {
let nextNode = head ? head.next : null;
let currNode = head;
let prevNode = null;
while (currNode) {
currNode.next = prevNode;
prevNode = currNode;
currNode = nextNode;
nextNode = nextNode ? nextNode.next : null;
}
return prevNode;
};


在這個版本的程式碼中,我們使用了條件運算符來確保在頭節點是唯一節點時,`nextNode` 不會是 `null`。我們還使用了 `currNode` 來判斷是否還有節點需要處理,並在每次迭代結束時更新它。最後,我們返回 `prevNode`,它現在是新的頭節點,因為它是原始鏈表的最後一個節點。
不明
【**此則訊息已被站方移除**】
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友回答

立即登入回答