求链表的倒数第m个元素陈越
时间: 2024-03-30 10:28:55 浏览: 18
倒数第m个元素可以通过快慢指针的方式来实现。具体步骤如下:
1. 定义两个指针,分别为fast和slow,初始时都指向链表的头节点。
2. 将fast指针向后移动m个位置。
3. 同时移动fast和slow指针,直到fast指针到达链表末尾。
4. 此时slow指针所指向的节点即为链表的倒数第m个元素。
以下是一个示例代码实现:
```cpp
class ListNode {
public:
int val;
ListNode* next;
ListNode(int value) {
val = value;
next = nullptr;
}
};
ListNode* findNthFromEnd(ListNode* head, int m) {
if (head == nullptr || m <= 0) {
return nullptr;
}
ListNode* slow = head;
ListNode* fast = head;
// 将fast指针向后移动m个位置
for (int i = 0; i < m; i++) {
if (fast == nullptr) {
return nullptr; // 如果链表长度小于m,返回空指针
}
fast = fast->next;
}
// 同时移动fast和slow指针,直到fast指针到达链表末尾
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow;}
```