C实现单向链表反序遍历，复杂度：o(n)

今天有空，静下心来写了一下单向链表的实现，重点在于单向链表的反序遍历复杂度可以为o(n)，这在以前没有想过，甚至认为单向链表无法反序遍历。本次实现了2种反序遍历方法。第一种比较简单，但是改变了链表的方向，第2种用了while嵌套。其它的内容可以供初学者学习一下，纯属抛砖引玉，有错误之处敬请批评指正。

源码环境：linux

编译方法：gcc --std=c99 single-list.c

single-list.h:

/****************************************************
***功能 : 单向链表[无tail指针]
***作者 : yycode
***日期 : 2017/06/17
****************************************************/

#ifndef __SINGLE_LIST__
#define __SINGLE_LIST__

#include <stddef.h>
#include <stdlib.h>

#define FREE(p) do{ \
 if(NULL != p){ \
  free(p); \
  p = NULL; \
 }    \
}while(0)

//node structure
typedef struct node{
 int value;
 struct node *next;
}t_node;

//list structure
typedef struct list{
 struct node *head;
// struct node *tail;
 uint32_t size;
}t_list;

t_list *create_list();
t_list *append_node(t_list *lst, int value);
t_node *back_node(t_list *lst);
t_node *find_node(t_list *lst, int value);
t_list *delete_node(t_list *lst, int value);
void traverse_list(t_list *lst);
void reverse_traverse1(t_list *lst);
void reverse_traverse2(t_list *lst);
void destroy_list(t_list **lst);

#endif

single-list.c

/****************************************************
***功能 : 单向链表[无tail指针]
***作者 : yycode
***日期 : 2017/06/17
****************************************************/
#include <time.h>
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <stdbool.h>
#include "single-list.h"

const uint32_t list_capacity = 10;

//创建
t_list *create_list(){
 t_list *lst = (t_list*)malloc(sizeof(t_list));
 assert(NULL != lst);
 lst->head = NULL;
 lst->size = 0;
 return lst;
}
//附加节点:【o(n)】
t_list *append_node(t_list *lst, int value){
 t_node *index = lst->head;
 t_node *node = (t_node*)malloc(sizeof(t_node));
 assert(NULL != lst);
 node->value = value;
 node->next = NULL;

 if(NULL == index){
  lst->head = node;
  ++lst->size;
  return lst;
 }
 while(NULL != index->next){
  index = index->next;
 }
 index->next = node;
 ++lst->size;
}
//获取末节点
t_node *back_node(t_list *lst){
 if(NULL == lst){
  return NULL;
 }
 t_node *find = lst->head;
 while(NULL != find->next){
  find = find->next;
 }
 return find;
}
//查找节点【o(n)】
t_node *find_node(t_list *lst, int value){
 t_node *index = lst->head;
 while(NULL != index && index->value != value){
  index = index->next;
 }
 if(NULL != index && index->value == value){
  return index;
 }
 return NULL;
}
//删除节点【o(n)】
t_list *delete_node(t_list *lst, int value){
 if(NULL == lst->head){
  return lst;
 }
 t_node *preindex = NULL;
 t_node *index = lst->head;
 while(NULL != index && index->value != value){
  preindex = index;
  index = index->next;
 }
 if(NULL != index && index->value == value){
  preindex->next = index->next;
  FREE(index);
  --lst->size;
 }
 return lst;
}
//遍历
void traverse_list(t_list *lst){
 t_node *index = lst->head;
 while(NULL != index){
  printf("traverse value = %d.\n", index->value);
  index = index->next;
 }
}
//反序遍历1:【2*o(n)】
void reverse_traverse1(t_list *lst){
 if(NULL == lst->head){ //空表
  printf("list content is empty!");
  return;
 }
 t_node *index = lst->head; //当前node
 t_node *front = NULL; //当前node前驱
 t_node *next = index->next;  //当前节点next
 //[o(n)]
 while(NULL != next){
  index->next = front; //update index->next
  front = index; //update front
  index = next; //update current
  next = index->next; //update next
 }
 index->next = front;
 lst->head = index; //update list->head
 
 //print list [o(n)]
 t_node *index2 = lst->head;
 while(NULL != index2){
  printf("reverse traverse1 value= %d.\n", index2->value);
  index2 = index2->next;
 }
}
//反序遍历2:【o(n) + o(n2)】
void reverse_traverse2(t_list *lst){
 if(NULL == lst->head){
  printf("list is empty!");
  return;
 }
 t_node *pretail = lst->head;
 t_node *tail = back_node(lst); //找到末节点[o(n)]
 while(tail != lst->head){ //【o(n2)】
  printf("reverse traverse2 value = %d.\n", tail->value);
  while(pretail->next != tail){
   pretail = pretail->next;
  }
  tail = pretail;
  pretail = lst->head;
 }
 printf("reverse traverse2 value = %d.\n", tail->value);
}
//销毁【o(n)】
void destroy_list(t_list **lst){
 t_list *list = *lst;
 if(NULL == list->head){ //链表为空
  FREE(*lst);
  return;
 }
 t_node *node = list->head;
 t_node *index = NULL;
 while(NULL != node){
  index = node->next;
  FREE(node);
  node = index;
 }
 list->head = NULL;
 list->size = 0;
 FREE(*lst);
}

//测试入口
int main()
{
 printf("=====<test single list>=====\n");

 srand((unsigned)time(NULL)); //后面要用随机数
 t_list *list = create_list();

 printf("\ninit list:capacity = %d\n", list_capacity);
 for(int i = 1; i <= list_capacity; ++i){
  append_node(list, i);
 }
 printf("sizeof(list) = %u.\n", list->size);

 unsigned rx = rand() % (list_capacity);
 printf("\ndelete value = %d from list:\n", rx);
 delete_node(list, rx);
 printf("sizeof(list) = %u.\n", list->size);
 
 printf("\ntraverse list:\n");
 traverse_list(list);
 
 printf("\nreverse1 traverse list:\n");
 reverse_traverse1(list);

 printf("\nreverse2 traverse list:\n");
 reverse_traverse2(list);

 printf("\nfind node from list:\n");
 rx = rand() % (list_capacity << 1);
 printf("find value = %d from list:", rx);
 t_node *find = find_node(list, rx);
 if(NULL != find)
  printf ("OK.\n");
 else
  printf ("FAIL!\n");
 rx = rand() % (list_capacity << 1);
 printf("find value = %d from list:", rx);
 find = find_node(list, rx);
 if(NULL != find)
  printf ("OK.\n");
 else
  printf ("FAIL!\n");
 
 destroy_list(&list);
 printf("\ndestroy list:\n");

 return 0;
}