原地反置链表(非递归和递归)

链表定义如下:

struct Node
{
	struct Node* next;
	int data;
};

非递归反置链表如下:

struct Node* ll_reverse(struct Node* head)
{
	if(head==NULL)
	{
		return NULL;
	}
	else
	{
		struct Node* pre = NULL;
		struct Node* next = NULL;
		struct Node* ptr = head;
		while(ptr!=NULL)
		{
			next = ptr->next;
			ptr->next = pre;
			pre = ptr;
			ptr = next;
		}
		head->next = NULL;
		return pre;
	}
}

递归反置如下:

struct Node* ll_reverse_rec(struct Node* head)
{
	if(head==NULL || head->next==NULL)
	{
		return head;
	}
	else
	{
		struct Node* ptr = ll_reverse_rec(head->next);
		head->next->next = head;
		head->next = NULL;
		return ptr;
	}
}

怎么感觉递归倒麻烦了呢……

 

Leave a Reply

Your email address will not be published.