019 Remove Nth Node From End of List[M]

02-16

1 題目描述

Given a linked list, remove the nth node from the end of list and return its head.
Note:
Given n will always be valid.

Try to do this in one pass.

難度：Medium

2 題目樣例

Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

3 題意分析

刪除鏈表倒數第n個節點，同時提示了可以一次遍歷完成。

4 思路分析

1 兩次遍歷

很容易想到的思路，第一次遍歷得到長度，第二次遍歷刪除節點。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { int len = 0; ListNode* ptr=head; ListNode tohead(0); tohead.next = head; while(ptr){ len++; ptr = ptr->next; } ptr = &tohead; while(ptr&&len!=n){ len--; ptr = ptr->next; } ptr->next = ptr->next->next; return tohead.next; }};

整體時間複雜度 $O(n)$ ，空間複雜度 $O(1)$

2 一次遍歷

一次遍歷需要兩個指針ptr1和ptr2。

首先我們讓ptr1指向head，ptr2指向使得區間[ptr1...ptr2]長度為n的節點，然後對區間整體向後移動，當ptr2指向尾節點的時候ptr1就指向了要刪除的節點。

不過這裡為了方便刪除，可以讓區間長度為n+1，同時ptr1從指向頭節點的節點開始。

代碼如下

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode tohead(0); ListNode* first = &tohead; ListNode* second = head; tohead.next = head; for(int i=1;i<n;i++) second=second->next; while(second->next){ first = first->next; second = second->next; } first->next = first->next->next; return tohead.next; }};

整體時間複雜度依舊是 $O(n)$ ，空間複雜度 $O(1)$ 。

5 後記

個人覺得這個優化並不是很必要，但是兩個指針的思想值得學習。