牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

单向链表反转

题目：已知单向链表的头结点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-01-06 07:10 杨粼波 阅读(5745) 评论(1)  编辑 收藏 引用

评论

# re: 单向链表反转 2011-01-25 16:26 Bowen

方法一没有写完吧，不然传head指针和他的指针引用就没有区别了
head->next = NULL;
head = pPrev;  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理