剑指Offer算法题-反转链表

发布于 / 刷题 / Comments Off on 剑指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;  
}

转载原创文章请注明,转载自: 斐斐のBlog » 剑指Offer算法题-反转链表
评论已关闭