Given a linked list, remove the n-th node from the end of list and return its head.
Example:
1 | Given linked list: 1->2->3->4->5, and n = 2. |
Note:
Given n will always be valid.
Follow up:
Could you do this in one pass?
两趟算法
一趟算法
用两个指针，一个快指针先走n+2步．指向第n+2个节点．随后慢指针也从头节点出发，两个指针一起向前走．当快指针到达链表尾后节点时，慢指针指向的节点和尾后节点之间隔着n个节点，即慢指针指向倒数第n+1个节点．
这时候只需要删除慢指针指向的下一个节点即可．
有几种情况需要考虑：
- 当链表中的总节点个数少于n个．无法删除倒数第n个节点．
- 当链表中的总结点个数等于n个．要被删除的正好是头结点．
- 当链表中的总结点个数大于n个．删除倒数第n个节点．
首先让快指针先走，要么走到第n+2个节点，要么走到尾后节点．
快指针先走之后，通过判断快指针共走过的节点个数来分情况处理．
若快指针共走过k个节点(包括最后一个尾后空节点)
- 若k<=n，说明链表中节点个数少于n，快指针走过的节点中包括了尾后节点(空节点)
- 若k==n+1，说明链表中节点个数为n，要删除的正是头结点
- 若k==n+2，说明链表中至少有n+1个非空节点，可以删除倒数第n个节点．
AC代码
1 |