数据结构链表遍历C语言

1、单链表中头结点有两个作用：一是标识该链表的存在，而是可以通过头结点遍历整个链表。所以不能通过移动头结点指针遍历链表，因为一旦移动了，下次就无法定位该链表。

2、例程：

#include "stdio.h"

#include "stdlib.h"

#define NULL 0

#define Error 0

typedef struct LNode{

int data

struct LNode *next

}LNode,*LinkList

LinkList CreatList(LinkList,int)

LinkList CreatList(LinkList L,int n)

 

{

LinkList p

int i

L=(LinkList)malloc(sizeof(LNode))

L->next=NULL

for(i=ni>0--i){

p=(LinkList)malloc(sizeof(LNode))

scanf("%d",&p->data)

p->next=L->next

L->next=p

}

return L

 

}

void Getelem(LinkList L)

 

//遍历链表

{

LinkList q

q=L->next

for(q->nextqq=q->next)

printf("%d",q->data)

}

 

void main(){

LinkList L

int a

 

puts("请输入链表长度：")

scanf("%d",&a)

L=CreatList(L,a) //L要接收函数返回指针

Getelem(L)

 

}

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

}

---