#2.链表的倒数第k个节点

2017-06-06

要求：

找到一个单向链表的倒数第k个节点。

考虑：

1 . 空链表
2 . k的输入是否合法

知识点：

1 . 创建链表：可以拆解为不断在当前链表后追加一个节点的操作。
链表尾节点：NODE *ptr;
创建1个节点：NODE *new_node = new NODE; new_node->data = val;
把该节点接到尾节点之后：ptr->next = new_node;
2 . 倒数第k个节点：由于是单向链表，所以没办法倒着遍历。
策略1：第一轮遍历所有节点，得出链表长度n；第二轮向前走n-k+1步，到达倒数第k个节点。（共走了: n+n-k+1步）
策略2：可以采用以前一后相隔（k-1）个节点的两个指针，同时向前推进，当走在前面的指针到达链表尾部时，后面的指针刚好到达倒数第k个节点。（两个指针也共走了:n+n-k+1步）
两种策略需要访问的节点数量是一样的，但是为什么第二种策略看起来更聪明呢？
因为策略1是顺序执行的，先走n步，然后再走n-k+1步。O(2n)
策略二可以并行执行：先走k-1步，然后两个指针再一起走n-k+1步。O(n)

代码：

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
/*
* Prob: 打印链表的倒数第k个节点
* Idea: 考虑各种情况：空链表，k不合法，创建链表，释放链表。
* Time: O(n)
* Space:O(n)
* Mistakes: 创建链表，指针应当先判断为空。ptr=nullptr时，访问ptr->next会报错。
* 2017-06-04
*/
#include<bits/stdc++.h>
using namespace std;
typedef struct Node{
    int n;
    struct Node* next;
}NODE;
// add a node after the pre_ptr
NODE* add_node(NODE* pre_ptr, int data){
    NODE* nd = new NODE;
    nd->n = data;
    nd->next = nullptr;
    pre_ptr->next = nd;
    return nd;
}
// create a link list
NODE* create_linklist(NODE*head, int length){
    NODE *ptr;
    ptr = new NODE;
    head = ptr;
    for(int i=1; i<=length; i++){
        ptr = add_node(ptr, i);
    }
    ptr->next = nullptr;
    return head;
}
// release the link list
void release_linklist(NODE*head){
    NODE *ptr=head, *q;
    while(ptr!=nullptr){
        q = ptr;
        delete ptr;
        ptr = q->next;
    }
    return;
}
// output the link list
void print_linklist(NODE* head){
    NODE* ptr = head->next;
    while(ptr != nullptr){
        cout<<ptr->n<<'\t';
        ptr = ptr->next;
    }
    cout<<endl;
}
// output the
void back_k_node(NODE* head, int k){
    // null
    if(head == nullptr) {cout<<"Link list is null!"<<endl; return;}
    // k < 1
    if(k <= 0) {cout<<"k should be greater than 0!"<<endl; return;}
    NODE *ptr1, *ptr2;
    ptr1 = ptr2 = head->next;
    for(int i=0; i<k-1; i++){
        // k > num
        if(ptr1 == nullptr) {break;}
        ptr1 = ptr1->next;
    }
    if(ptr1 == nullptr) {cout<<k<<" is larger than the linklist size!"<<endl; return;}
    while(ptr1->next != nullptr){
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    cout<<k<<"th ele is: "<<ptr2->n<<endl;
    return;
}
// main func
int main(){
    NODE* head = nullptr;
    int num = 19;
    int test_units[10] = {0, -1, -20, 5, 1, 10, 7, 11, 22, 100};
    head = create_linklist(head, num);
    print_linklist(head);
    for(int i=0; i<10; i++)
        back_k_node(head, test_units[i]);
    release_linklist(head);
    return 0;
}