学步园

复习一下链表反转

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

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

#include <stdio.h>
#include <malloc.h>

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;
}