Leetcode算法系列（链表）之删除链表倒数第N个节点

难度：中等
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

Python实现

# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution(object):
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
"""
方法一：
1. 复制表头元素head1=head
2. 遍历单链表
将当前节点复制为head2
遍历当前节点后n个元素
若不够n个元素就到达链表末尾，返回整个链表恰好n位，删除首节点即可，即返回首节点下一节点
head2后移
若head2后移n个元素之后正好为空，则删除该节点head下一节点
返回表头元素head1
"""
i = 0
head1 = head
while head:
head2 = head
j = 0
while j < n + 1:
if not head2:
return head1.next
head2 = head2.next
j += 1
if not head2:
head.next = head.next.next
return head1
i += 1
head = head.next

def removeNthFromEnd2(self, head: ListNode, n: int) -> ListNode:  
    """  
    一次遍历，滑动串口  
    """  
    fast = head  
    slow = head  
    for i in range(n):  
        fast = fast.next  
    if not fast:  
        # 链表长度为N的情况  
        return head.next

    while fast.next:  
        fast = fast.next  
        slow = slow.next  
    slow.next = slow.next.next  
    return head

def removeNthFromEnd3(self, head: ListNode, n: int) -> ListNode:  
    dummy = ListNode(0)  
    dummy.next = head  
    fast,slow = dummy,dummy  
    for  i in range(n+1):  
        fast = fast.next  
    while fast is not None:  
        fast = fast.next  
        slow = slow.next  
    slow.next = slow.next.next  
    return dummy.next

def create_listnode(list1: list) -> ListNode:
print(list1)
list1_nodes = [ListNode(x=node) for node in list1]
i = 0
while i < len(list1) - 1:
list1_nodes[i].next = list1_nodes[i + 1]
i += 1

return list1\_nodes\[0\]

def print_lnode(lnode):
while lnode:
print(lnode.val)
lnode = lnode.next

if __name__ == "__main__":
l1 = create_listnode(list1=[1,2,3,4,5])
solution = Solution()
# head = solution.removeNthFromEnd(head=l1, n=1)
head = solution.removeNthFromEnd2(head=l1, n=2)
# if head.__class__ == ListNode:
print_lnode(head)

Go语言实现

package main

import "fmt"

// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}

func (h *ListNode) Show() {
fmt.Println(h.Val)
for h.Next != nil {
h = h.Next
fmt.Println(h.Val)
}
}

func removeNthFromEnd1(head *ListNode, n int) *ListNode {
// 快慢指针法 先让快指针领先n个位置
// 当快指针到达nil时 慢指针即倒数第n个位置
// 0 ms 2.2 MB Golang
node := &ListNode{Next: head}
fast, slow, step := node, node, 0
for step < n {
fast = fast.Next
step++
}
for fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return node.Next
}

func removeNthFromEnd2(head *ListNode, n int) *ListNode {
// 数组循环存储最后N个元素，一次遍历
// 题目规定“给定的 n 保证是有效的。”所以不对n进行检查了
// 0 ms 2.2 MB Golang
var length int = n + 1
var tempNodes []*ListNode = make([]*ListNode, length)
var countNode int = 0
var tail *ListNode = head
for tail != nil {
tempNodes[countNode%length] = tail
tail = tail.Next
countNode++
}
if countNode == n { // 最后一个节点的情况
return head.Next
}
if n == 1 { // 第一个节点的情况
tempNodes[countNode%length].Next = nil
} else { // 中间的情况
tempNodes[countNode%length].Next = tempNodes[(countNode+2)%length]
}
return head
}

func removeNthFromEnd3(head *ListNode, n int) *ListNode {
// 两次遍历
// 0 ms 2.2 MB Golang
if head.Next == nil {
return nil
}
node := &ListNode{Next: head}
pointer, pointer2, length := node, node, 1
for pointer.Next != nil {
pointer = pointer.Next
length++
}
index := length - n
for i := 1; i <= length; i++ {
if i == index {
if pointer2.Next == nil {
break
}
pointer2.Next = pointer2.Next.Next
break
} else {
pointer2 = pointer2.Next
}
}
return node.Next
}

func removeNthFromEnd4(head *ListNode, n int) *ListNode {
// 递归实现 0 ms 2.2 MB Golang
head, _ = handler(head, 1, n)
return head
}

func handler(head *ListNode, layer, n int) (*ListNode, int) {
if head == nil {
return head, layer - 1
}
next, maxNum := handler(head.Next, layer+1, n)
if layer == maxNum-n+1 {
return head.Next, maxNum
} else if layer == maxNum-n {
head.Next = next
return head, maxNum
} else {
return head, maxNum
}
}

func create_link_list(list1 []int) *ListNode {
head := &ListNode{Val: list1[0]}
tail := head
for i := 1; i < len(list1); i++ {
tail.Next = &ListNode{Val: list1[i]}
tail = tail.Next
// head.Append(list1)
}
return head
}

func main() {
l1 := []int{1, 2, 3, 4, 5}
fmt.Println(l1)
head1 := create_link_list(l1)
head2 := removeNthFromEnd4(head1, 2)
head2.Show()
}

执行结果

方法

执行用时

内存消耗

语言

python-遍历判断

40 ms

13.9 MB

Python3

python-快慢指针，滑动窗口

40 ms

13.8 MB

Python3

GO-快慢指针，滑动窗口

0ms

2.2MB

Golang

Go-数组存储，一次遍历

0ms

2.2MB

Golang

Go-两次遍历

0ms

2.2MB

Golang

Go-递归实现

0ms

2.2MB

Golang