剑指offer-JZ15

反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11168&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

输入一个链表,反转链表后,输出新链表的表头。
c++

两种思路:暴力法,双指针法;

方法一:暴力
利用vector 保存每一个链表指针,然后逆向构建。
时间复杂度:图片说明
空间复杂度:图片说明
代码如下:

 class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // empty
        if(pHead == nullptr) return nullptr;
        //save listnode
        vector<ListNode*> vec;
        while(pHead != nullptr){
            vec.push_back(pHead);
            pHead = pHead->next;
        }
        //reverse(vec.begin(),vec.end());
        // create new head
        int n = vec.size()-1;
        ListNode *new_head = vec[n];
        ListNode *current = new_head;
        for(int i=n-1; i>=0; i--){
            current->next = vec[i];
            current = current->next;
        }
        current->next = nullptr;
        return new_head;
    }
};

方法二: 双指针法
利用两个相邻指针,维护更新连接的指向,从头至尾。
时间复杂度:图片说明
空间复杂度:图片说明
代码如下:

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        // empty
        if(!pHead) return nullptr;
        // creat two pointer;
        ListNode *pre = nullptr;
        ListNode *cur = pHead;
        ListNode *nex;
        while(cur){
            // save next point;
            nex = cur->next;
            // change current point;
            cur->next = pre;
            // update three point
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务