简明现代魔法 -> 数据结构 -> 几种实现链表逆序的方法

几种实现链表逆序的方法

2010-08-18

链表逆序就是把一个链表按照原来的链接顺序逆序实现(也就是将头变成尾,尾变成头)。

编程思路:其实最关键的是先通过原来的链接顺序找到下个节点,然后再把前个节点反序。

链表的头节点如下:

struct ListNode
{
	void*       m_nKey;
	ListNode* 	m_pNext;
}; 

常规实现:

ListNode* ReverseIteratively(ListNode* pHead)
{
	ListNode* pReversedHead = NULL;
	ListNode* pNode = pHead;
	ListNode* pPrev = NULL;
	while(pNode != NULL)
	{
		// get the next node, and save it at pNext
		ListNode* pNext = pNode->m_pNext;

   		// if the next node is null, the currect is the end of original
  		// list, and it's the head of the reversed list
    	if(pNext == NULL)
     		pReversedHead = pNode;

    	// reverse the linkage between nodes
    	pNode->m_pNext = pPrev;

   		// move forward on the the list
    	pPrev = pNode;
  		pNode = pNext;
   	}
}

递归实现(不需要临时节点):

ListNode* reverse_list( ListNode* head)       //逆序
{
	ListNode* new_head=head;
	if(head==NULL || head->next==NULL)
		return head;
	new_head = reverse_list(head->next);
	head->next->next=head;
	head->next=NULL; 	//防止链表成为一个环,这是最关键的。
	return new_head; 
}
随机文章推荐
网站分类


注:如需转载本文,请注明出处(原文链接),谢谢。更多精彩内容,请进入简明现代魔法首页。

进入新博客
喜欢本文,就分享它吧
给我留言
您的名字:
您的邮件:
您的网站:


 

copyright © 2009 简明现代魔法    学习、分享、进步

power by Gonn 感谢所有关心和支持本站的朋友们