首页 > 代码库 > IT公司100题-13-求链表中倒数第k个结点

IT公司100题-13-求链表中倒数第k个结点

2024-07-16 16:26:04   225人阅读

问题描述：

输入一个单向链表，输出该链表中倒数第k个结点。链表倒数第0个节点为NULL。
struct list_node {    int data;    list_node* next;};

分析：

方法1：
首先计算出链表中节点的个数n，然后倒数第k个节点，为正数n-k+1个节点。
需要遍历链表2次。
方法1代码实现：
 1 // 13_1.cc 2 #include <iostream> 3 using namespace std; 4  5 struct list_node { 6     int data; 7     list_node* next; 8 }; 9 10 list_node* find_kth(list_node* head, size_t k) {11     if (!head)12         return NULL;13 14     // 统计链表中节点的个数15     size_t count = 1;16     list_node* cur = head;17     while(cur->next != NULL) {18         cur = cur->next;19         count++;20     }21 22     if(count < k)23         return NULL;24 25     cur = head;26     for(size_t i = 1; i <= count - k; i++)27         cur = cur->next;28 29     return cur;30 }31 32 // 插入元素33 void insert_node(list_node*& head, int data) {34     list_node* p = new list_node;35     p->data =http://www.mamicode.com/ data;36     p->next = head;37     head = p;38 }39 40 int main() {41     // 创建链表42     list_node* head = NULL;43     for (int i = 10; i > 0; i--)44         insert_node(head, i);45 46     // 查找倒数第k个47     list_node* p = find_kth(head, 4);48     cout << p->data << endl;49     return 0;50 }

方法2：

使用双指针，第一个指针先走k步，然后两个指针一起走，直到第一个指针为NULL，则第一个指针便指向倒数第k个节点。
方法2实现代码：
 1 // 13_2.cc 2 #include <iostream> 3 using namespace std; 4  5 struct list_node { 6     int data; 7     list_node* next; 8 }; 9 10 list_node* find_kth(list_node* head, size_t k) {11     if (!head)12         return NULL;13 14     list_node* p1 = head;15     for (size_t i = 1; i <= k; i++) {16         if (!p1)  // 链表长度不足k17             return NULL;18         else19             p1 = p1->next;20     }21 22     list_node* p2 = head;23     while (p1) {24         p1 = p1->next;25         p2 = p2->next;26     }27     return p2;28 }29 30 // 插入元素31 void insert_node(list_node*& head, int data) {32     list_node* p = new list_node;33     p->data =http://www.mamicode.com/ data;34     p->next = head;35     head = p;36 }37 38 int main() {39     // 创建链表40     list_node* head = NULL;41     for (int i = 10; i > 0; i--)42         insert_node(head, i);43 44     // 查找倒数第k个45     list_node* p = find_kth(head, 4);46     cout << p->data << endl;47     return 0;48 }

转载自源代码

本文链接地址: http://w.worthsee.com/index.php/13-%e6%b1%82%e9%93%be%e8%a1%a8%e4%b8%ad%e5%80%92%e6%95%b0%e7%ac%ack%e4%b8%aa


联系
我们