首页 > 代码库 > 查找单链表的倒数第k个值

查找单链表的倒数第k个值

2024-07-04 17:39:35   230人阅读

          刚开始，我想到的是一种笨方法，先遍历单链表，计算出单链表的长度len，然后再从头遍历单链表到第len-k个节点，那么

这个节点既是单链表的倒数第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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
typedef struct list{
    int data;
    struct list *next;
}list_node,*listNode;
 
void createList(listNode &list,int arr[],int n)
{
    int i;
    listNode temp;
    for(i=0;i<n;i++)
    {
          temp=(list_node*)malloc(sizeof(list_node));     //为节点分配内存
          if(temp)
          {
               temp->data=http://www.mamicode.com/arr[i];
               temp->next=NULL;
               temp->next=list->next;
               list->next=temp;
          }
          else
          {
             cout<<"内存分配失败"<<endl;
          }
 
    }
}
/**
     查找倒数第k个节点
*/
int find_knode(listNode list,int k)
{
    if(list==NULL||k<0)
    {
        cout<<"链表不能为空或k值不能小于0"<<endl;
        return 0;
    }
    listNode first;
    listNode second;
    int i=0;
    first=list->next;
    second=list->next;
    while(i<k)
    {
        first=first->next;
        i++;
    }
    if(first==NULL)
    {
        cout<<"链表长度小于k"<<endl;
        return -1;
    }
    while(first)
    {
       first=first->next;
       second=second->next;
    }
    return second->data;
 
}
void  show_list(listNode list)
{
    listNode temp;
    temp=list;
    while(temp)
    {
        cout<<temp->data<<"---";
        temp=temp->next;
    }
}
 
int main(){
    int arr[]={12,3,6,1,9,17,19,21,22,87};
    listNode list=NULL;
    list=(list_node*)malloc(sizeof(listNode));
    list->data=http://www.mamicode.com/0;
    list->next=NULL;
    int k=6;
     
    int val;
    cout<<"创建链表:"<<endl;
    createList(list,arr,10);
    val=find_knode(list,k);
    cout<<"倒数第<<k<<个节点为:"<<val<<endl;
    cout<<"show list:"<<endl;
    show_list(list);
    return 0;
 
}

　　运行结果如下:

    

    在运行sublime text2时发现出现 error2的错误。

    解决办法如下：打开F:\SublimeText2\Data\Packages\C++\c++.sublime-build

    

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
    "cmd": ["g++", "${file}", "-o", "${file_path}/${file_base_name}"],
    "file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
    "working_dir": "${file_path}",
    "selector": "source.c, source.c++",
 
    "variants":
    [
        {
            "name": "Run",
            //"cmd": ["bash", "-c", "g++ ‘${file}‘ -o ‘${file_path}/${file_base_name}‘ && ‘${file_path}/${file_base_name}‘"]
            "cmd": [ "${file_path}/${file_base_name}.exe"]
        }
    ]
}

　　看到有注释的那一行，是原先配置的，现在把它注释掉，添加下面的一行：

           "cmd": [ "${file_path}/${file_base_name}.exe"]

      重新运行，就可以了。

   

 


联系
我们