[路飛]_leetcode 19. 刪除連結串列的倒數第 N 個結點、leetcode 83.刪除排序連結串列中的重複元素

語言: CN / TW / HK

「這是我參與11月更文挑戰的第 7 天,活動詳情檢視:2021最後一次更文挑戰

題目1

題目來源:LeetCode-19. 刪除連結串列的倒數第 N 個結點

給你一個連結串列,刪除連結串列的倒數第 n 個結點,並且返回連結串列的頭結點。

進階:你能嘗試使用一趟掃描實現嗎?

示例 1:

image.png

輸入:head = [1,2,3,4,5], n = 2\ 輸出:[1,2,3,5]

示例 2:

輸入:head = [1], n = 1\ 輸出:[]

示例 3:

輸入:head = [1,2], n = 1\ 輸出:[1]  

提示:

連結串列中結點的數目為 sz\ 1 <= sz <= 30\ 0 <= Node.val <= 100\ 1 <= n <= sz

提出問題

  • 連結串列進行節點刪除操作?

分析

  • 定義pre指標,指向虛擬頭節點,定義cur指標,

image.png

  • 使cur指標往前移動一位。

image.png

  • 重複執行上述操作,n次。

image.png

  • 同時移動 precur指標。

image.png

  • 重複執行上述操作,直到cur指標指向null

image.png

  • 使pre指標所指向pre指標下一個的一下節點,這樣就能把待刪除的節點給刪除掉。

image.png

程式碼實現

/** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { if(!head) return null let ret = new ListNode(-1,head) let pre = ret let cur = head while(n--) cur = cur.next while(cur){ pre = pre.next cur = cur.next } pre.next = pre.next.next return ret.next };

題目2

題目來源:LeetCode-83. 刪除排序連結串列中的重複元素

存在一個按升序排列的連結串列,給你這個連結串列的頭節點 head ,請你刪除所有重複的元素,使每個元素 只出現一次 。 返回同樣按升序排列的結果連結串列。

示例 1:

輸入:head = [1,1,2]\ 輸出:[1,2]\ 示例 2:

輸入:head = [1,1,2,3,3]\ 輸出:[1,2,3]  

提示:

連結串列中節點數目在範圍 [0, 300] 內\ -100 <= Node.val <= 100\ 題目資料保證連結串列已經按升序排列

提出問題

  • 如何判斷列表倆個的節點是否相同?

分析

初始化temp指標指向head節點

image.png

判斷temp指標所指節點的值與當前節點的下個節點的值是否一樣

image.png

一樣的話就使temp指標所指的節點指向當前節點下一個的下一個,否則進行往後移動

image.png

重複執行上述操作,直到temp指標所指的下一個節點為null

image.png

程式碼實現

js /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { if(!head) return null let ret = new ListNode(-1,head) let pre = ret let cur = head while(n--) cur = cur.next while(cur){ pre = pre.next cur = cur.next } pre.next = pre.next.next return ret.next };