剑指Offer算法题-反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

题解

一个很简单的办法是将所有指针节点存入一个vector中，然后再重新链接，这样的时间复杂度是2n，空间复杂度是n。

一个更好的办法是遍历链表，直接反转。代码如下

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(!pHead) return NULL;
        ListNode *NextPtr = pHead->next, *tmpHeadPtr = pHead;
        while(pHead){
            if(NextPtr == NULL){
                tmpHeadPtr->next = NULL;
                return pHead;
            }    
            ListNode* tmp = NextPtr->next;
            NextPtr->next = pHead;
            pHead = NextPtr;
            NextPtr = tmp;
        }
    }
};

如果想在本地测试一下，下面给出了本地测试可用的代码：

#include <bits/stdc++.h>
using namespace std;
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) { 
        }
};

ListNode* ReverseList(ListNode* pHead) {
    if(!pHead) return NULL;
    ListNode *NextPtr = pHead->next, *tmpHeadPtr = pHead;
    while(pHead){
        if(NextPtr == NULL){
            tmpHeadPtr->next = NULL;
            return pHead;
        }    
        ListNode* tmp = NextPtr->next;
        NextPtr->next = pHead;
        pHead = NextPtr;
        NextPtr = tmp;
    }
}

int main(){
    ListNode *head = new ListNode(0), *ptr = head;
    int N;
    cout << "输入多少数" << endl;
    cin >> N;
    cout << endl << "读取链表：" << endl; 
    for(int i = 0; i < N; i++){
        int num;
        cin >> num;
        ptr->next= new ListNode(num);
        ptr = ptr->next;
    }
    ListNode* p = head;
    cout << "反转前" << endl;
    while(p){
        cout << p->val << ' ';
        p = p->next;
    }
    cout << endl << "开始反转" << endl;
    p = ReverseList(head);
    cout << "反转后" << endl;
    while(p){
        cout << p->val << ' ';
        p = p->next;
    }
    return 0;  
}