Remove Nth Node From End of List
描述
Given a linked list, remove the n
-th node from the end of list and return its head.
For 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. - Try to do this in one pass.
分析
设两个指针p
,q
,让q
先走n
步,然后p
和q
一起走,直到q
走到尾节点,删除p->next
即可。
代码
// Remove Nth Node From End of List
// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
ListNode dummy{-1, head};
ListNode *p = &dummy, *q = &dummy;
for (int i = 0; i < n; i++) // q先走n步
q = q->next;
while(q->next != nullptr) { // 一起走
p = p->next;
q = q->next;
}
ListNode *tmp = p->next;
p->next = p->next->next;
delete tmp;
return dummy.next;
}
};