单链表的反转问题-创新互联

单链表的反转问题

单链表反转问题经常会遇到。在此记录一下，以便查阅方便。

如果反转一个有头结点的使用下面的方法比较合适。

//反转单链表，此单链表带有头节点。
//思想：使用tmp临时指针保存头结点与链表的关系
typedef struct ListNode 
{
	int data;
	struct ListNode * next;
}ListNode,*LinkList;
void ReverseList(ListNode* Head)
{
	ListNode *current,*tmp;
	current = Head->next;
	if(current != NULL)//反转后第一个节点的后继要为NULL
	{
		tmp = current;
		current = current->next;
		tmp->next = NULL;
	}
	
	while(current!=NULL)
	{
		tmp = current;
		current = current->next;
		tmp->next = Head->next;
		Head->next = tmp;
	}
}

如果没有头结点，下面的反转比较合适

//如果没有头节点，下面的函数比较适合
//思想：使用pre和next两个指针来记录当前处理的节点的前一个节点和后一个节点的信息
ListNode * ReverseLinkList(ListNode * head)
{
	ListNode * pre,*next;
	pre = NULL;
	next = NULL;
	while(head)
	{
		next = head->next;
		head->next = pre;
		pre = head;
		head = next;
	}
	return pre;
}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。