删除链表的倒数第N个结点（go语言）

题目描述：

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

题目链接：力扣

 

提示：

链表中结点的数目为 sz1 <= sz <= 300 <= Node.val <= 1001 <= n <= sz

go语言题解：

方法一：计算链表长度。

思路：先将 head 的长度计算出来，接着遍历链表，要删除倒数第二个，那么就是删除第

length-n+1 个。代码如下：

func GetLength(head *ListNode) (length int) {
	len:=0
	for head!=nil {
		head=head.Next
		len++
	}
	return len
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	length:= GetLength(head)
	newList:=&ListNode{0,head}
	cur:=newList//相当于是一个游标
	for i := 0; i < length-n; i++ {
		cur=cur.Next//让游标一个一个往下走
	}
	cur.Next=cur.Next.Next
	return newList.Next
}

方法二： 栈，代码如下：

//方法二：栈
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	nodes := []*ListNode{}
	dummy := &ListNode{0, head}
	for node := dummy; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}
	prev := nodes[len(nodes)-1-n]
	prev.Next = prev.Next.Next
	return dummy.Next
}

方法三 ：快慢指针。

思路：双指针，慢指针指向被删除的前一个结点。代码如下：

//方法三：快慢指针
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	first, second := head, dummy
	for i := 0; i < n; i++ {
		first = first.Next
	}
	for ; first != nil; first = first.Next {
		second = second.Next
	}
	second.Next = second.Next.Next
	return dummy.Next
}

不过要想自己测试的话，可以写 show 方法的进行自我测试：全部代码如下：

package main

import "fmt"
//方法一：计算链表长度
type ListNode struct {
	Val int
	Next *ListNode
}

func GetLength(head *ListNode) (length int) {
	len:=0
	for head!=nil {
		head=head.Next
		len++
	}
	return len
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	length:= GetLength(head)
	newList:=&ListNode{0,head}
	cur:=newList//相当于是一个游标
	for i := 0; i < length-n; i++ {
		cur=cur.Next//让游标一个一个往下走
	}
	cur.Next=cur.Next.Next
	return newList.Next
}

func (head *ListNode) Show()  {
	fmt.Print(head.Val)
	for head.Next!=nil {
		head=head.Next
		fmt.Print(head.Val)
	}
}
func main()  {
	list:=[] int{1,2,3,4,5}
	head:=&ListNode{Val: list[0]}
	cur:=head
	for i := 1; i 

 

 

 

欢迎分享，转载请注明来源：内存溢出

原文地址:https://54852.com/langs/994799.html