# 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)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()
}