【剑指Offer】JZ24反转链表(C++)

【剑指Offer】JZ24反转链表(C++),第1张

【剑指Offer】JZ24反转链表(C++) 题目地址:反转链表_牛客题霸_牛客网 题目: 描述

给定一个单链表的头结点pHead,长度为n,反转该链表后,返回新链表的表头。

数据范围: nleq1000n≤1000

要求:空间复杂度 O(1)O(1) ,时间复杂度 O(n)O(n) 。

如当输入链表{1,2,3}时,

经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。

以上转换过程如下图所示:

示例1

输入:

{1,2,3}

返回值:

{3,2,1}
示例2

输入:

{}

返回值:

{}

说明:

空链表则输出空    
代码:
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==NULL)return NULL;
        ListNode* t=new ListNode(-1);
        ListNode* p1=pHead;
        ListNode* p2=p1->next;
        if(p2==NULL)return pHead;
        ListNode* p3=p2->next;
        if(p3==NULL)
        {
            t=p2;
            t->next=p1;
            p1->next=NULL;
            return t;
        }
        ListNode* g;
        p2->next=p1;
        p1->next=NULL;
        while(p3!=NULL){
            g=p3->next;
            p3->next=p2;
            p2=p3;
            p3=g;
        }
        t=p2;
        return t;
    }
};
解题思路:

就是把每个结点的next改成前一个结点,注意特殊例子就行。

头结点直接是第一个点,不是空结点。

 

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5097356.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-11-16
下一篇 2022-11-16

发表评论

登录后才能评论

评论列表(0条)

保存