By Leo_璇哥

更新日期:

文章目录

设计一个算法，找出一个无环的单链表里面倒数第k个元素。

  • 首先，检查链表是否为空，以及检查输入的k的有效性。
  • 其次，考虑单链表少于K个元素的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct node{    
    int key;    
    node* next;    
};    
typedef node* List;    
int findLastKthElement(List list, int k)    
{    
    //遍历整个链表，    
    //声明一个临时指针指向头节点    
    //当遍历过元素个数小于K的时候，继续遍历    
    //当遍历过的元素个数等于k的时候，临时指针指向下一个元素，然后继续遍历    
    //当遍历到链表尾部的时候，则临时指针指向的节点就为倒数第k个元素。    
    if (list == NULL || k <= 0)    
    {    
        return -1;   //查找失败。    
    }    
    List p = list;    
    List tempList = list;    
    int num = 0;    
    while(p)    
    {    
        if (num < k)    
        {    
            num++;    
        }    
        else if (num == k)    
        {    
            tempList = tempList->next;    
        }    
        p = p->next;    
    }    
        
    if (num < k)    
    {    
        return -1; //查找倒数第k个元素失败    
    }    
    return  tempList->key;    
}
文章目录