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 = new ListNode(-1);
dummy.next = head;
ListNode p = dummy, q = dummy;
for (int i = 0; i < n; i++) // q先走n步
q = q.next;
while(q.next != null) { // 一起走
p = p.next;
q = q.next;
}
p.next = p.next.next;
return dummy.next;
}
}