[程序员面试题精选100题]19.反转链表

题目

输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

分析

假设经过若干操作，我们已经把结点 pre之前的指针调整完毕，这些结点的next指针都指向前面一个结点。现在我们遍历到结点cur。我们需要把调整结点的next指针让它指向前一个结点pre。注意一旦调整了指针的指向，链表就断开了，如下图所示：

因为已经没有指针指向结点nextNode，我们没有办法再遍历到结点nextNode 了。因此为了避免链表断开，我们需要在调整cur的next指针之前要把nextNode保存下来。

代码

/*---------------------------------------------
*   日期：2015-02-11
*   作者：SJF0115
*   题目: 19.反转链表
*   来源：程序员精选100题
*   博客：
-----------------------------------------------*/
#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL){}
};

// 输出
void Show(ListNode *head){
    ListNode *p = head;
    while(p){
        cout<<p->val<<"->";
        p = p->next;
    }//while
    cout<<"nullptr"<<endl;
}

class Solution {
public:
    void ReverseList(ListNode* &head){
        if(head == NULL){
            return;
        }//if
        ListNode *pre = NULL,*cur = head,*nextNode;
        while(cur){
            nextNode = cur->next;
            cur->next = pre;
            // 前移一个节点
            pre = cur;
            cur = nextNode;
        }//while
        head = pre;
    }//void
};


int main() {
    Solution solution;
    ListNode *head = new ListNode(1);
    ListNode *node,*p;
    p = head;
    for(int i = 2;i <= 8;++i){
        node = new ListNode(i);
        p->next = node;
        p = node;
    }//for
    Show(head);
    solution.ReverseList(head);
    Show(head);
}

代码二

ListNode* Reverse(ListNode* head){
        if(head == nullptr){
            return nullptr;
        }//if
        // 头结点
        ListNode *dunny = new ListNode(0);
        ListNode *p = head,*cur = nullptr;
        while(p){
            // 记住p的下一节点
            cur = p->next;
            // 头插入法
            p->next = dunny->next;
            dunny->next = p;
            p = cur;
        }//while
        return dunny->next;
    }

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>