首页 > 代码库 > 笔试算法题（08）：输出倒数第K个节点

笔试算法题（08）：输出倒数第K个节点

2024-07-05 00:16:16   227人阅读

出题：输入一个单向链表，要求输出链表中倒数第K个节点

分析：利用等差指针，指针A先行K步，然后指针B从链表头与A同步前进，当A到达链表尾时B指向的节点就是倒数第K个节点；

解题：

 1 struct Node {
 2         int v;
 3         Node *next;
 4 };
 5 Node* FindLastKth(Node *head, int k) {
 6         if(head==NULL) {
 7                 printf("\nhead is NULL\n");
 8                 exit(0);
 9         }
10         Node *first=head, *second=head;
11         int step=1;
12         /**
13          * 由于链表末尾没有哑节点，所以注意边界关系，
14          * first实际上是先走了k-1步
15          * */
16         for(int i=1;i<k;i++) {
17                 if(first->next != NULL) {
18                         first=first->next;
19                         step++;
20                 }
21         }
22         /**
23          * 注意判断当链表长度小于k的情况
24          * */
25         if(step<k) {
26                 printf("\nlist is shorter than k\n");
27                 exit(0);
28         }
29         /**
30          * first和second同步前进
31          * */
32         while(first->next != NULL) {
33                 first=first->next;
34                 second=second->next;
35         }
36         return second;
37 }

 


联系
我们