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

题目地址 #

解题思路 #

常规法 #

先计算链表长度，比如是 length。那么删除倒数第 n 个节点，也就是删除顺数第 length-n+1 个节点，设为 s，直接从 1 找到第 s-1 个也就是 s 的上一个节点（其实也就是 length-n），直接把 s-1 删除即可。

双指针法 #

TODO

具体实现 #

Go常规法

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return head
	}

	length := 0
	tmpc := head
	for tmpc != nil {
		//fmt.Println(tmpc.Val)
		length++
		tmpc = tmpc.Next
	}

	// 需要有虚拟头结点是因为，可能删除的是最后的节点，也就是头结点，用虚拟头结点可以统一处理
	dummy := &ListNode{
		Val:  0,
		Next: head,
	}

	cur := dummy
	// 注意这里 i 是从 1 开始
	for i := 1; i < length-n+1; i++ {
		cur = cur.Next
	}
	cur.Next = cur.Next.Next
	return dummy.Next
}

func main() {
	ret := removeNthFromEnd(&ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val:  5,
						Next: nil,
					},
				},
			},
		},
	}, 2)
	fmt.Println(ret)
}

Go双指针

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if head == nil {
		return head
	}

	dummy := &ListNode{
		Next: head,
	}

	fast, low := dummy, dummy
	// fast 先移动 n 步
	for n != 0 && fast != nil {
		fast = fast.Next
		n--
	}
	// fast 再移动一步，这样当 fast 为 nil 时，low 在 n 的上一位
	fast = fast.Next
	for fast != nil {
		fast = fast.Next
		low = low.Next
	}
	low.Next = low.Next.Next
	return dummy.Next
}

func main() {
	ret := removeNthFromEnd(&ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val:  5,
						Next: nil,
					},
				},
			},
		},
	}, 2)
	fmt.Println(ret)
}

参考 #

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