LeetCode偶爾一題 —— 19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)（鏈表系列）

Anshiii 發(fā)布于2019-08-26 10:21 / 3198人閱讀

摘要：題目描述給定一個(gè)鏈表，刪除鏈表的倒數(shù)第個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。示例給定一個(gè)鏈表和當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)楹?jiǎn)單的思路用一個(gè)數(shù)組保存所有的鏈表節(jié)點(diǎn)，遍歷完之后可以知道倒數(shù)第個(gè)鏈表節(jié)點(diǎn)。

題目描述

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
示例：

給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.  
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.

簡(jiǎn)單的思路

用一個(gè)數(shù)組保存所有的鏈表節(jié)點(diǎn)，遍歷完之后可以知道倒數(shù)第 n 個(gè)鏈表節(jié)點(diǎn)。
時(shí)間復(fù)雜度 為 O(k)，空間復(fù)雜度 為 O(k)，這里 k 為鏈表長(zhǎng)度。

進(jìn)階

使用兩個(gè)指針，快指針先遍歷 n 個(gè)節(jié)點(diǎn)，之后兩個(gè)指針再一起遍歷，等到快指針遍歷結(jié)束后，慢指針指向的當(dāng)前節(jié)點(diǎn)就是倒數(shù)第 n 個(gè)節(jié)點(diǎn)。
時(shí)間復(fù)雜度 為 O(k)，空間復(fù)雜度 為 O(1)，這里 k 為鏈表長(zhǎng)度。

??注意：為了寫代碼方便，我們可以在鏈表頭節(jié)點(diǎn)前加多一個(gè)節(jié)點(diǎn)。

示例代碼：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let temp = { next: head }
    temp.next = head
    let p = q = temp
    for (let i = 0; i <= n; i++) {
        p = p.next
    }
    while(p) {
        p = p.next
        q = q.next
    }
    q.next = q.next.next
    return temp.next
};

原題地址: https://leetcode-cn.com/probl...
代碼不定時(shí)更新，歡迎 star 我的 repo

掃描下方的二維碼或搜索「tony老師的前端補(bǔ)習(xí)班」關(guān)注我的微信公眾號(hào)，那么就可以第一時(shí)間收到我的最新文章。