单向链表反转(转)

转自于http://www.cppblog.com/tx7do/archive/2009/01/06/71280.html

题目:已知单向链表的头结点head,写一个函数把这个链表逆序 ( Intel)


解答:
我们假设单向链表的节点如下:
template <typename T>
class list_node
{
public:
list_node 
* next;
T data;
}
;

这个题目算是考察数据结构的最基础的题目了,有两种方法可以解此题:

方法一:
    void reverse(node*& head)
    
{
        
if ( (head == 0|| (head->next == 0) ) return;// 边界检测
        node* pNext = 0;
        node
* pPrev = head;// 保存链表头节点
        node* pCur = head->next;// 获取当前节点
        while (pCur != 0)
        
{
            pNext 
= pCur->next;// 将下一个节点保存下来
            pCur->next = pPrev;// 将当前节点的下一节点置为前节点
            pPrev = pCur;// 将当前节点保存为前一节点
            pCur = pNext;// 将当前节点置为下一节点
        }

    }

这是一般的方法,总之就是用了几个临时变量,然后遍历整个链表,将当前节点的下一节点置为前节点。


方法二:
    node* reverse( node* pNode, node*& head)
    
{
        
if ( (pNode == 0|| (pNode->next == 0) ) // 递归跳出条件
        {
            head 
= pNode; // 将链表切断,否则会形成回环
            return pNode;
        }


        node
* temp = reserve(pNode->next, head);// 递归
        temp->next = pNode;// 将下一节点置为当前节点,既前置节点
        return pNode;// 返回当前节点
    }
这个方法是采用了递归算法,也就是在反转当前节点之前先反转其后继节点,说白了其实就是利用函数的调用堆栈构建了一个临时链表罢了,挺废的一个算法,权当作是写着好玩,没有什么实在的意义。
采用此算法需要注意的是,头结点必须要传入的是引用,因为在递归跳出的时候要切断链表,否则链表将会形成一个回环。

posted on 2009-05-12 17:51 蒋耘 阅读(3810) 评论(1)  编辑  收藏 所属分类: 数据结构与算法

评论

# re: 单向链表反转(转)[未登录] 2013-08-29 00:39 fornever

方法一中尾节点(翻转前的头结点)Next未置为NULL  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航:
 
<2013年8月>
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜