给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
思路:双指针
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
//搞个头结点
node:=&ListNode{0,head}
// 双指针
prev,pn:=node,node
// 第二个指针先完后移n,那么第二个指针移到底的时候,第一个指针就是我们要删除的节点
// 两个指针同时向后移动
for i:=1;i<=n+1;i++{
pn=pn.Next
}
// 第二个指针没到底之前,两个指针一起后移
for pn!=nil {
prev=prev.Next
pn=pn.Next
}
// 删除第一个指针对应的next
prev.Next=prev.Next.Next
// 输出啦
return node.Next
}