LeetCode之刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)
前言
我們社區(qū)陸續(xù)會(huì)將顧毅(Netflix 增長(zhǎng)黑客，《iOS 面試之道》作者，ACE 職業(yè)健身教練。微博:@故胤道長(zhǎng)[1])的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。
LeetCode 算法到目前我們已經(jīng)更新了 18 期，我們會(huì)保持更新時(shí)間和進(jìn)度(周一、周三、周五早上 9:00 發(fā)布)，每期的內(nèi)容不多，我們希望大家可以在上班路上閱讀，長(zhǎng)久積累會(huì)有很大提升。
不積跬步，無以至千里;不積小流，無以成江海，Swift社區(qū) 伴你前行。
難度水平：中等
1. 描述
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
2. 示例
示例 1
- 輸入：head = [1,2,3,4,5], n = 2
- 輸出：[1,2,3,5]
示例 2
- 輸入：head = [1], n = 1
- 輸出：[]
示例 3
- 輸入：head = [1,2], n = 1
- 輸出：[1]
約束條件：
- 鏈表中結(jié)點(diǎn)的數(shù)目為 sz
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
3. 答案
- class RemoveNthFromEnd {
- func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
- let dummy = ListNode(0)
- dummy.next = head
- var prev: ListNode? = dummy
- var post: ListNode? = dummy
- // move post
- for _ in 0..<n {
- post = post!.next
- }
- // move prev and post at the same time
- while post!.next != nil {
- prev = prev!.next
- post = post!.next
- }
- prev!.next = prev!.next!.next
- return dummy.next
- }
- }
- 主要思想：運(yùn)動(dòng)員技術(shù)
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
該算法題解的倉(cāng)庫：LeetCode-Swift[2]
點(diǎn)擊前往 LeetCode[3] 練習(xí)
關(guān)于我們Swift社區(qū)是由 Swift 愛好者共同維護(hù)的公益組織，我們?cè)趪?guó)內(nèi)以微信公眾號(hào)的運(yùn)營(yíng)為主，我們會(huì)分享以 Swift實(shí)戰(zhàn)、SwiftUl、Swift基礎(chǔ)為核心的技術(shù)內(nèi)容，也整理收集優(yōu)秀的學(xué)習(xí)資料。
參考資料
[1] @故胤道長(zhǎng):
https://m.weibo.cn/u/1827884772
[2] LeetCode-Swift:
https://github.com/soapyigu/LeetCode-Swift
[3] LeetCode:
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
