查找单向链表倒数第k个位置上的结点。 在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k(k > 0)个位置的节点。 /** * Definition for singly-linked list. * struct Node { * int val; * Node * next; * Node(int x) : val(x), next(NULL) {} * }; */
时间: 2023-12-26 08:03:16 浏览: 25
可以采用双指针的方法来查找单向链表中倒数第k个位置的节点。
首先定义两个指针p和q,将它们都指向链表的头节点。然后让指针q先向后移动k个位置,接着同时移动指针p和q,直到指针q到达链表的末尾位置。此时指针p所指向的节点即为链表倒数第k个位置的节点。
具体实现如下:
```c++
Node* findKthToTail(Node* head, int k) {
if (head == nullptr || k <= 0) {
// 链表为空或k无效,返回nullptr
return nullptr;
}
Node* p = head;
Node* q = head;
for (int i = 0; i < k; i++) {
if (q == nullptr) {
// 链表长度小于k,返回nullptr
return nullptr;
}
q = q->next;
}
while (q != nullptr) {
p = p->next;
q = q->next;
}
return p;
}
```
时间复杂度为O(N),空间复杂度为O(1)。
相关问题
查找链表中倒数第k个位置上的结点 C语言实现
要实现查找链表中倒数第k个位置上的节点,可以使用双指针法。
首先,定义两个指针p和q,初始时都指向链表的头节点。然后,将指针p向前移动k个位置,使得p指向链表中的第k个节点。
接下来,同时移动指针p和q,直到p指向链表的末尾节点。此时,q所指向的节点即为链表中倒数第k个位置上的节点。
下面是一个示例的C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 查找链表中倒数第k个位置上的节点
Node* findKthFromEnd(Node* head, int k) {
if (head == NULL || k <= 0) {
return NULL;
}
Node* p = head;
Node* q = head;
// 将指针p向前移动k个位置
for (int i = 0; i < k; i++) {
if (p == NULL) {
return NULL; // 链表长度小于k
}
p = p->next;
}
// 同时移动指针p和q
while (p != NULL) {
p = p->next;
q = q->next;
}
return q;
}
// 创建链表
Node* createLinkedList(int arr[], int n) {
if (n <= 0) {
return NULL;
}
Node* head = (Node*)malloc(sizeof(Node));
head->data = arr[0];
head->next = NULL;
Node* tail = head;
for (int i = 1; i < n; i++) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = arr[i];
newNode->next = NULL;
tail->next = newNode;
tail = newNode;
}
return head;
}
// 打印链表
void printLinkedList(Node* head) {
Node* p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 销毁链表
void destroyLinkedList(Node* head) {
Node* p = head;
while (p != NULL) {
Node* temp = p->next;
free(p);
p = temp;
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
Node* head = createLinkedList(arr, n);
printf("原链表:");
printLinkedList(head);
int k = 2;
Node* kthNode = findKthFromEnd(head, k);
if (kthNode != NULL) {
printf("倒数第%d个位置上的节点的值为:%d\n", k, kthNode->data);
} else {
printf("链表长度小于%d\n", k);
}
destroyLinkedList(head);
return 0;
}
```
上述代码中,首先创建了一个链表,然后调用findKthFromEnd函数查找倒数第k个位置上的节点,并打印出该节点的值。
注意:在实际使用中,需要对输入的数据进行合法性检查,以确保程序的健壮性。
已知一个带头节点的单链表,结点结构为(data,next),假设该链表只给出了头指针l,在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置的结点(k为正整数)。若查找成功,算法
如下:
1. 定义两个指针p和q,初始时均指向头节点l。
2. 让指针p先走k步,此时指针q和指针p之间的距离为k。
3. 然后同时移动指针p和指针q,每次移动一步,直到指针p到达链表末尾。
4. 此时指针q所指向的节点即为倒数第k个节点。
算法的时间复杂度为O(n),其中n为链表的长度。