单链表查找k节点 遍历一次链表

1、如果能从链表尾部开始遍历，那只需倒序遍历 k 个节点即是要找出的节点，但是由于是单链表，只能从头结点开始遍历。

2、先遍历一遍该单链表，获取链表的总节点数 n，那么第 n-k+1 这个节点就是倒数第 k 个节点。所以第二次再遍历到第 n-k+1 这个节点即可，但是题目要求只能遍历一遍链表。

3、通过遍历该链表把节点都存入到一个数组中，然后再通过数组下标可直接获取到倒数第 k 个节点，但是这样会需要额外的存储空间，空间复杂度为 O(n)。

额。。写完了才发现好像题目意思理解错了，是倒序遍历啊，不过我已经把整个链表倒过来了，直接遍历即可，遍历完了可以再倒回去。。。= =要不你就按原本的顺序遍历，每次都插入到最前面，这样就新建一个链表和原本顺序相反，就可以了～

========================================================

#include <stdio.h>

#include <stdlib.h>

typedef struct _node {

int value

struct _node *next

} node

node * make_node(int value) {

node *new_node = (node *) malloc(sizeof(node))

new_node->value = value

new_node->next = 0

return new_node

}

node * add_after(node *pos, int value) {

node *new_node = make_node(value)

pos->next = new_node

return new_node

}

void print_node_list(node *head) {

while (head) {

printf("%d ", head->value)

head = head->next

}

printf("\n")

}

void free_node_list(node *head) {

node *temp

while (head) {

temp = head

head = head->next

free(temp)

}

}

node * reverse(node *head) {

node *f = 0, *s = 0

while (head) {

f = s

s = head

head = head->next

s->next = f

}

return s

}

int main() {

int i = 0

node *head = make_node(i), *last = head

while (i <10) {

last = add_after(last, ++i)

}

print_node_list(head)

head = reverse(head)

print_node_list(head)

free_node_list(head)

return 0

}

---