查找链表倒数第k个结点
时间: 2023-11-21 18:06:32 浏览: 99
查找链表倒数第k个结点可以使用双指针法。首先定义两个指针p1和p2,都指向链表的头结点。然后将p1指针向前移动k个结点,此时p1和p2之间的距离为k。接着同时移动p1和p2指针,直到p1指向链表的末尾,此时p2指向的结点即为倒数第k个结点。
具体实现代码如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_kth_to_tail(head: ListNode, k: int) -> ListNode:
if not head or k <= 0:
return None
p1 = p2 = head
for i in range(k-1):
if not p1.next:
return None
p1 = p1.next
while p1.next:
p1 = p1.next
p2 = p2.next
return p2
```
其中,head为链表的头结点,k为倒数第k个结点的位置,函数返回倒数第k个结点。如果链表为空或k小于等于0,返回None。
相关问题
第9关:查找链表倒数第k个结点
题目描述:给定一个链表,输出该链表倒数第k个节点,如果k大于链表长度则返回空。
算法思路:使用双指针,先让第一个指针移动k-1个节点,然后再让第一个指针和第二个指针同时移动,当第一个指针到达链表结尾时,第二个指针指向的就是倒数第k个节点。
参考代码实现(Python):
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findKthToTail(head, k):
if head is None or k <= 0:
return None
# 定义两个指针,初始都指向头结点
p1 = p2 = head
# 让第一个指针移动k-1个节点
for i in range(k-1):
if p1.next is None:
return None
p1 = p1.next
# 两个指针同时移动,直到第一个指针到达链表结尾
while p1.next is not None:
p1 = p1.next
p2 = p2.next
return p2
```
参考代码实现(Java):
```java
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode findKthToTail(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
// 定义两个指针,初始都指向头结点
ListNode p1 = head;
ListNode p2 = head;
// 让第一个指针移动k-1个节点
for (int i = 0; i < k-1; i++) {
if (p1.next == null) {
return null;
}
p1 = p1.next;
}
// 两个指针同时移动,直到第一个指针到达链表结尾
while (p1.next != null) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
```
查找链表倒数第n个结点
查找链表倒数第n个节点是一种常见的链表操作,可以使用双指针法来解决。这种方法涉及两个指针,通常称为快指针(fast)和慢指针(slow)。以下是步骤:
1. **初始化**:
- 将快指针设置为链表头节点,快指针先走两步;
- 将慢指针设置为链表头节点,只走一步。
2. **移动指针**:
- 当快指针到达链表尾部(即空节点或下一个节点为空)时,慢指针会停在倒数第二个节点上;
- 因为快指针每次走两步,所以当它到达尾部时,慢指针恰好走了n步。
3. **找到倒数第n个节点**:
- 返回慢指针指向的节点,这就是我们要找的倒数第n个节点。
如果你需要实现这个算法,这是一个伪代码示例:
```python
def find_kth_to_last(head, n):
fast = head
slow = head
for _ in range(n):
if fast is not None:
fast = fast.next
else:
return None # 如果链表长度小于n,返回None
while fast is not None:
fast = fast.next
slow = slow.next
return slow
```
阅读全文