单链表中删除倒数第n个节点的技巧
发布时间: 2024-04-12 10:02:39 阅读量: 8 订阅数: 19
# 1. 理解单链表和节点操作
单链表是一种数据结构,由若干个节点组成,每个节点包含数据和指向下一个节点的指针。相比数组,单链表的插入和删除操作更为高效,但访问元素的随机性较差。节点通常由数据域和指针域组成,节点之间通过指针连接成链表。遍历单链表需要从头节点开始,依次向后遍历每个节点,直到尾节点为止。单链表的优点是插入和删除元素不需要移动其他元素,但查找元素时间较长。掌握节点的基本操作是理解单链表的关键,包括节点的插入、删除和修改。通过遍历节点,可以逐个访问链表中的每个元素。
# 2. 寻找倒数第n个节点的算法
- **遍历两次法**
- 算法思路
倒数第n个节点即为正数第L-n+1个节点,其中L为链表长度。遍历两次法的思路是先遍历一次链表统计节点个数,然后再遍历至第L-n+1个节点。这样便能找到所需节点。
- Python 实现示例
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def findNthFromEnd(head, n):
length = 0
cur = head
while cur:
length += 1
cur = cur.next
k = length - n
cur = head
for _ in range(k):
cur = cur.next
return cur.val
```
- **双指针法**
- 算法原理
双指针法使用两个指针,第一个指针先移动n步,然后第二个指针与第一个指针同步移动,当第一个指针到达末尾时,第二个指针即为倒数第n个节点。
- Java 实现代码演示
```java
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public int findNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.
```
0
0