本文共 7472 字，大约阅读时间需要 24 分钟。

问：

题目：《》

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

答：

方法一 ：利用一个切片记录所有的指针

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.3 MB, 击败了7.14%的用户

func removeNthFromEnd1(head *ListNode, n int) *ListNode {
   	var data []*ListNode	node := head	// 将所有节点的计入切片	for {
   		data = append(data, node)		if node.Next == nil {
   			break		}		node = node.Next	}	// 排除没有数据或者只有一个值，删掉的也是一个	l := len(data)	if l == 0 || l < n || (l == 1 && n == 1) {
   		return nil	}	// 切片定位到n的位置	node = data[l-n]	// 已经到最后一个了，只能往前找，让前一个节点的Next为nil	if node.Next == nil {
   		node = data[l-n-1]		node.Next = nil	} else {
   		node.Val = node.Next.Val		node.Next = node.Next.Next	}	return head}

方法二 ：循环第一遍找到节点数量，循环第二遍找到总数-n的节点

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了35.7%的用户

func removeNthFromEnd2(head *ListNode, n int) *ListNode {
   	node := head	l := 0	// 合计节点数量	for {
   		l++		if node.Next == nil {
   			break		}		node = node.Next	}	// 排除没有数据或者只有一个值，删掉的也是一个	if l == 0 || l < n || (l == 1 && n == 1) {
   		return nil	}	// 找到n的节点位置，删除	node = head	temp := head	for i := 0; i < l; i++ {
   		if l-n == i {
   			// 已经到最后一个了，只能往前找，让前一个节点的Next为nil			if node.Next == nil {
   				node = temp				node.Next = nil				break			} else {
   				node.Val = node.Next.Val				node.Next = node.Next.Next				break			}		}		temp = node		node = node.Next	}	return head}

方法三 ：思路和方法二一致，但少了变量

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了64.29%的用户

func removeNthFromEnd3(head *ListNode, n int) *ListNode {
   	node := head	l := 0	// 合计节点数量	for {
   		l++		if node.Next == nil {
   			break		}		node = node.Next	}	// 排除没有数据或者只有一个值，删掉的也是一个	if l == 0 || l < n || (l == 1 && n == 1) {
   		return nil	}	// 找到n的节点位置，删除	node = head	for i := 0; i < l; i++ {
   		if n == 1 && i+2 == l {
   			// 已经到最后一个了，只能往前找，让前一个节点的Next为nil			node.Next = nil			break		}		if l-n == i {
   			node.Val = node.Next.Val			node.Next = node.Next.Next			break		}		node = node.Next	}	return head}

方法四 ：利用递归

因为平台在公共变量部分有bug，所以只能使用闭包递归的方法。也正好顺便学习一下。 执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd4(head *ListNode, n int) *ListNode {
   	// 定义函数	type funcType func(*ListNode, int) *ListNode	var ra funcType	isBack := 1	ra = func(head *ListNode, n int) *ListNode {
   		// 到底退回		if head.Next == nil {
   			if n-isBack <= 0 {
   				return nil			}			return head		}		// 只删除最后一个		if n == 1 && head.Next.Next == nil {
   			head.Next = nil			return head		}		// 递归开始		ra(head.Next, n)		// 定位到n的位置再删除		isBack++		if n-isBack == 0 {
   			head.Val = head.Next.Val			head.Next = head.Next.Next		}		return head	}	// 执行闭包并返回	return ra(head, n)}

方法五 ：利用递归，改进了方法四

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd5(head *ListNode, n int) *ListNode {
   	// 就一个直接返回空	if n == 1 && head.Next == nil {
   		return nil	}	// 定义一个函数类型	type funcType func(*ListNode)	// 声明	var ra funcType	// 创建一个递归函数	ra = func(head *ListNode) {
   		// 如果就切割最后一个		// 不能写成if head.Next.Next==nil && n==1{，否则在某些条件里会内存溢出		if n == 1 && head.Next.Next == nil {
   			head.Next = nil			return		}		// 到达最后一层则返回		if head.Next == nil {
   			return		}		// 递归		ra(head.Next)		// 减少一层		n--		// 到达返回指定位置则去掉该位置的节点		if n == 1 {
   			head.Val = head.Next.Val			head.Next = head.Next.Next		}		return	}	// 执行	ra(head)	// 返回	return head}

方法六 ：双指针

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd6(head *ListNode, n int) *ListNode {
   	// 就一个直接返回空	if n == 1 && head.Next == nil {
   		return nil	}	// 初始化	nodeI, nodeJ, x := head, head, head	// 如果n==1，那么s为1	s := 0	if n == 1 {
   		s = 1	}	// 指针定位到n的位置	for ; nodeI.Next != nil; nodeI = nodeI.Next {
   		n--		// 第一个指针到达指定位置，开始定位第二个指针		if n < 1 {
   			// x每次都记录当前的节点指针，则在循环结束的时候，x永远是nodeJ的前一个节点			x = nodeJ			nodeJ = nodeJ.Next		}	}	// 判断是否删除最后一个	if s == 1 {
   		x.Next = nil	} else {
   		nodeJ.Val = nodeJ.Next.Val		nodeJ.Next = nodeJ.Next.Next	}	return head}

方法七 ：双指针进化版

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd7(head *ListNode, n int) *ListNode {
   	// 就一个直接返回空	if n == 1 && head.Next == nil {
   		return nil	}	nodeJ := head	// 指针定位到n的位置	for nodeI := head; nodeI != nil; nodeI = nodeI.Next {
   		// 第一个指针到达指定位置，开始定位第二个指针		if n < 1 {
   			// 判断是否是只删除最后一个			if nodeJ.Next.Next == nil {
   				nodeJ.Next = nil			} else {
   				nodeJ = nodeJ.Next			}		}		n--	}	// 不是最后一个才进行删除，如果是只删除最后一个则已经在for循环中完成	if nodeJ.Next != nil {
   		*nodeJ = *(nodeJ.Next)	}	return head}

方法八 ：双指针加入哨兵节点

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd8(head *ListNode, n int) *ListNode {
   	// 就一个直接返回空	if n == 1 && head.Next == nil {
   		return nil	}	// 创建一个哨兵节点	var nodeJ = &ListNode{
   		Val:  0,		Next: head,	}	// 指针定位到n的位置	for nodeI := head; nodeI != nil; nodeI = nodeI.Next {
   		// 第一个指针到达指定位置，开始定位第二个指针		if n < 1 {
   			nodeJ = nodeJ.Next		}		n--	}	// for循环已经定位完成，但并没有到达n的位置，是倒数n+1的位置	if nodeJ.Next.Next != nil {
   		nodeJ.Next.Val = nodeJ.Next.Next.Val		nodeJ.Next.Next = nodeJ.Next.Next.Next	} else {
   		nodeJ.Next = nil	}	return head}

方法九 ：双指针加入哨兵节点变化版

相较于方法八少了循环时的条件判断，循环总次数一致，但分为两次循环 执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd9(head *ListNode, n int) *ListNode {
   	if n == 1 && head.Next == nil {
   		return nil	}	nodeI := head	var nodeJ = &ListNode{
   		Val:  0,		Next: head,	}	// nodeI先走n步	for i := 0; i < n; i++ {
   		nodeI = nodeI.Next	}	// nodeJ开始走，直到nodeI将剩余的链表走完，nodeJ就定位在n-1的位置	for ; nodeI != nil; nodeI = nodeI.Next {
   		nodeJ = nodeJ.Next	}	// 如果[n-1,n+1]这三个位置都有节点，则删除n位后，n+1位自动靠前	// 如果n+1的位置没有节点，则删除n后，n-1的nodeJ.Next需要改为nil，以链表，否则越界	if nodeJ.Next.Next == nil {
   		nodeJ.Next = nil	} else {
   		*(nodeJ.Next) = *(nodeJ.Next.Next)	}	return head}

方法十 ：双指针加入哨兵节点进阶

执行用时 :0 ms, 击败了100.00%的用户 内存消耗 :2.2 MB, 击败了100.00%的用户

func removeNthFromEnd10(head *ListNode, n int) *ListNode {
   	// 创建一个ListNode，并返回指针	nodeTemp := new(ListNode)	// 连上head，此刻的nodeTemp为头部哨兵节点	nodeTemp.Next = head	// 初始化快慢指针，与哨兵一致	nodeI, nodeJ := nodeTemp, nodeTemp	// 循环n+1次，快指针定位到n+1的节点位置	for i := 0; i <= n; i++ {
   		nodeI = nodeI.Next	}	// 从n+1的位置起循环至链表结束，循环次数为(l+1)-(n+1)	// 原链表节点数为l，因为增加了一个哨兵节点，所以总数为l+1	// 这样最终的循环次数为l-n，慢指针定位在l-n的位置，其实就是倒数n+1的位置	for ; nodeI != nil; nodeI = nodeI.Next {
   		nodeJ = nodeJ.Next	}	//将倒数n+1的位置的Next（即倒数n位置）替换成倒数n-1的位置，相当于将n位置删除	nodeJ.Next = nodeJ.Next.Next	// 返回哨兵节点的下一个，	// 一般情况下相当于返回head即可	// 但如果题目为[1]1，则表示第一个节点删除，	// 如果此时返回head，则为[1]	// 如果返回nodeTemp.Next，则为[]	// 原理是当第一次循环（i），循环2次，i分别为0、1，此时nodeI定位在了最后的节点，也就是值为1	// 第二次循环由于不满足条件nodeI!=nil，因此不进行循环	// 然后nodeJ.Next=nodeJ.Next.Next,此时的nodeJ仍旧是在哨兵节点，因此，他的nodeJ.Next替换的值就是nil	// 最后要返回nodeTemp.Next，则为nil	return nodeTemp.Next}

解：

方法一耗费内存最多，其它的方法执行效率和内存占用都差不多。

利用双指针的方式最为高效，其中双指针外加哨兵节点的话，更能减少for循环中的判断语句，理论上应该更快，在方法十中已经没有条件语句了，速度更快。

这道题几个解题思路涉及如下知识点：

1. 双指针
   一个快指针，一个慢指针。
   快慢之间的间隔根据题目要求来，比如快指针按照一次一层来走，慢指针一次二层；
   本题的快指针一次一层走了n步后，慢指针再出发，但也是一次一层。

参考：

《》

---

2. 哨兵节点
   
   在解本题时候有几种特别要注意情况：

• 如果n和链表节点数量一致，也就是要删除第一个节点；
• 如果n是1，即删除最后一个；
• 如果n是1，节点也只有一个，即全部删除

在做本题时，经常遇到越界，不得不一个个排除，直到最后留下了上面的三种情况，开始是用if条件语句来过滤或者临时变量来过渡，直到最后发现了可以使用哨兵节点~~

参考：

《》

---

3. 闭包递归
   在做字符串题目时对递归纠结了很长时间，因此现在遇到有分支、层级递进并且需要退回的操作时，第一反应就是递归，这道题很明显符合这种特征：

• 分支层级：链表的自带属性~~分支和层级；
• 层层递进：不像数组等，可以直接定位到索引位置，链表只能层层前进，才能到达需要的位置；
• 需要退回：到达最后一个节点后再退回到n的节点位置；
• 退回操作：每层退回时都可能存在操作，本题在退回时需要判断节点是否到达n位并进行删除操作。

We’ve written >100k lines of Go code and it has come up maybe once. That kind of frequency doesn’t suggest that a language change is warranted.

意思就是说，在实际编码中遇到需要这种特性的几率很小很小，所以没有必要直接在语言层面去支持，如果偶然遇到就使用替代方案吧

参考：

《》 《》

转载地址：http://otkpi.baihongyu.com/