删除链表倒数第n个元素
要实现一个链表并删除链表的倒数第n个元素，首先需要定义链表的节点结构，然后实现链表的基本操作，包括插入元素和删除元素。以下是使用Python语言实现链表并删除倒数第n个元素的示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def append(self, value):
new_node = ListNode(value)
if not self.head:
self.head = new_node
else:
current = self.node
while current.next:
current = current.next
current.next = new_node
def print_list(self):
current = self.head
while current:
print(current.value, end=" -> ")
current = current.next
print("None")
def delete_nth_from_end(self, n):
dummy = ListNode(0)
dummy.next = self.head
fast = dummy
slow = dummy
# 将fast指针向前移动n+1个位置
for _ in range(n+1):
if fast:
fast = fast.next
# 同时移动fast和slow指针，直到fast到达链表末尾
while fast:
fast = fast.next
slow = slow.next
# 删除倒数第n个节点
if slow.next:
slow.next = slow.next.next
# 更新链表头
self.head = dummy.next
# 示例用法
linked_list = LinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
print("原始链表:")
linked_list.print_list()
n = 2
linked_list.delete_nth_from_end(n)
print(f"删除倒数第{n}个元素后的链表:")
linked_list.print_list()
|
在这个示例中，首先定义了一个ListNode类来表示链表节点，每个节点包含一个value属性用于存储节点的值，以及一个next属性用于指向下一个节点。然后，定义了一个LinkedList类来表示链表，它包含一些基本操作，如append用于在链表末尾添加元素，print_list用于打印链表中的元素，以及delete_nth_from_end用于删除链表的倒数第n个元素。
在delete_nth_from_end方法中，使用了快慢指针的技巧。首先，创建了一个虚拟节点dummy，并将其next指针指向链表的头节点。然后，我们将快指针fast向前移动n+1个位置，这样快指针和慢指针之间就保持了n个节点的距离。接下来，同时移动快指针和慢指针，直到快指针到达链表末尾。此时，慢指针指向的节点就是倒数第n+1个节点，可以通过修改慢指针的next指针来删除倒数第n个节点。最后，更新链表的头节点为虚拟节点的下一个节点。
在示例用法中，创建了一个链表并添加了5个元素。然后，调用delete_nth_from_end方法来删除链表的倒数第2个元素，并打印删除元素后的链表。
参考