1.題目

Given a linked list, remove the?n-th node from the end of list and return its head.

Example:

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.

Note:

Given?n?will always be valid.

2.中文翻譯

給定鏈接列表，從列表末尾刪除第n個節(jié)點(diǎn)并返回其頭部。
例：
給出鏈表：1-> 2-> 3-> 4-> 5，n = 2。
從末尾刪除第二個節(jié)點(diǎn)后，鏈表變?yōu)?-> 2-> 3-> 5。
注意：

給定n將始終有效。

3.解析

處理這種問題，我們首先考慮的是時間復(fù)雜度和空間復(fù)雜度的問題，利用有限的資源，有效的解決問題才是我們鍛煉的目的。在這里，可以定義一個節(jié)點(diǎn)p和q，同時指向頭結(jié)點(diǎn)，用一個變量k（k初始位0）跟進(jìn)鏈表節(jié)點(diǎn)的位置，當(dāng)k<0時，p不移動，否則移動，此外，保證q是一直移動的，這樣，在q移到末尾時，p剛好移動到倒數(shù)第n個位置。這其實(shí)利用到了對稱性原理，可以畫圖更好的理解。

4.算法代碼：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode p=head,q=head; int k=0; while (q!=null){if (q.next==null){if (k+1==n) head=head.next; else p.next=p.next.next; }if (k<n) k++; else p=p.next; q=q.next; }return head; } }

5.提交結(jié)果

總結(jié)

以上是生活随笔為你收集整理的LeetCode上删除链表末尾第N个节点算法——Remove Nth Node From End of List的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。