老卫带你学---leetcode刷题(19. 删除链表的倒数第 N 个结点)

19. 删除链表的倒数第 N 个结点

问题：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：


输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
1
2
3
4
5

示例 2：

输入：head = [1], n = 1
输出：[]
1
2
3
4

示例 3：

输入：head = [1,2], n = 1
输出：[1]
1
2
3
4

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
1
2
3
4
5
6

解决：

没啥说的，两个指针，一起向后移动，类似剑指offer的14题老卫带你学—剑指offer刷题系列(14.链表中倒数第k个结点)

不过这里需要注意两个点：

• 因为需要删除该节点，其实要寻找的是上一个节点的位置，那么基准就需要用n+1
• 要考虑一种边界情况，n就是链表长度，这时候需要用l来丈量是否到链表头

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	current := head
	l:=0 //这里是精髓，需要考虑一种边界情况，n就是你链表的长度，这时候下面就会越界
	s:=n+1
	for s>0{
		if current!=nil{
			current=current.Next
			s-=1
			l+=1
		} else{
			if l==n{ //这道题的唯一陷阱，需要在这里考虑这种l==n的边界情况
				return head.Next
			}
			return nil
		}
	}
	backup := head
	for current!=nil{
		current=current.Next
		backup=backup.Next
	}
	backup.Next=backup.Next.Next
	return head
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24