复习一下链表反转

分别用递归的方法和非递归的方法实现。

链表反转中通过借助辅助参数，可以用两个指针完成反转 Node* Reverse2Point(List* head)

#include 
  
   
#include 
   
     typedef int ElemType; typedef struct Node { int data; struct Node* next; }Node, *List; //用数组arr来初始化链表中数据；此例中链表无头点 int InitList(List *list, ElemType* arr, int num) { int i= 0; Node* tail_node; Node* tmp_node; *list =(List)malloc(sizeof(Node)); if(NULL == *list) return; (*list)->data = arr[i]; (*list)->next = NULL; tail_node = *list; for(i = 1; i < num; i++) { tmp_node = (Node*)malloc(sizeof(Node)); if(NULL == tmp_node) return; tmp_node->data = arr[i]; tmp_node->next = NULL; tail_node->next = tmp_node; tail_node = tmp_node; } } void TraveseList(List list) { Node* tmp_node; if(NULL == list) return; tmp_node = list; while(tmp_node) { printf("%d ", tmp_node->data); tmp_node = tmp_node->next; } printf("\n"); } void ReverseList(List* list) { Node* p_pre = NULL; Node* p_cur = NULL; Node* p_nxt = NULL; if(NULL == list) return; p_cur = (*list)->next; p_pre = *list; p_pre->next = NULL; while(p_cur) { p_nxt = p_cur->next; p_cur->next = p_pre; p_pre = p_cur; p_cur = p_nxt; } *list = p_pre; } Node* Reverse2Point(List* head) { Node* p_cur = NULL; Node* p_nxt = NULL; if(NULL == *head) return; p_cur = (*head)->next; (*head)->next = NULL; while(p_cur) { p_nxt = p_cur->next; p_cur->next = *head; *head = p_cur; p_cur = p_nxt; } } //递归实现反转，返回反转后的链表头 //原理同上述非递归方法，反转当前节点和该节点的指针（反转前分别保存当前节点和该节点的下一个节点，以便完成后续节点相同的操作--通过递归完成） Node* Reverse(Node* p_cur, Node* p_pre) { if(NULL == p_cur->next) { p_cur->next = p_pre; return p_cur; } else { Node *p_nxt = p_cur->next; p_cur->next = p_pre; Reverse(p_nxt, p_cur); } } int main() { List head; Node* tmp; int array[] = {3, 5, 7, 8, 2}; InitList(&head, array, 5); TraveseList(head); printf("reverse list:"); ReverseList(&head); TraveseList(head); printf("reverse list:"); head = Reverse(head, NULL); TraveseList(head); printf("reverse list:"); Reverse2Point(&head); TraveseList(head); return 0; }