【无标题】

【无标题】,第1张

给定一个单链表的头结点head(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

数据范围: 0\leq n\leq10000≤n≤1000

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

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

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

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

 

解法一:迭代法

遍历链表,使当前指针cur指向它的前一个节点,但此时由于cur指针指向前一个节点,会丢失cur节点的下一个节点的信息,必须先对当前指针cur的下一个节点信息作为记录,当遍历结束后,我们返回当前指针cur的上一个节点,此时cur节点的上一个节点刚好是我们需要返回新链表的表头。

//迭代方式
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;//当前节点
        ListNode* prev = NULL;//上一个节点
        ListNode* tmp = NULL;//当前节点指向上一个节点的时候,记录当前节点的下一个节点
        while(cur!=NULL)
        {
            tmp=cur->next;
            cur->next=prev;
            prev = cur;
            cur=tmp;
        }
        return prev;//此时当前节点指向最后一个节点的下一个节点
                    //即当前节点为空,prev节点是我们需要返回的新节点

    }
};

解法二:递归法

 当我们达到递归所能划分的最小子问题时,再次递归已经没有意义,此时我们归,反转函数。使用递归函数,一直递归到链表的最后一个结点,该结点就是反转后的头结点,记作 p
此后,函数返回时,让当前指针的下一个节点的next域指向head,同时将head的next域置为NULL
从而实现从链表尾部开始的局部反转,当递归函数全部出栈后,链表反转完成。

//递归实现
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
       //递归终止条件  剩下一个节点的时候返回head
       if( head==NULL || head->next==NULL)
       {
           return head;
       }
    ListNode* p = reverseList(head->next);  //当最p指向最后一个节点
        //递归归的过程
        head->next->next = head;
        head->next = NULL; 

        return p;
    }
};

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

原文地址:http://outofmemory.cn/langs/921865.html

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

随机推荐

  • 2017年美国国匹兹堡艺术学院特色

    匹兹堡艺术学院成立于1921年,为了适应当时的社会环境应运而生,起初以广告商业学为主导课程,后来经过不断发展,逐渐增开了其他课程,可授予学士学位、副学士学位,除了专业课的学习外,还开设一般通识课程,与

    2022-07-07
    000
  • 2017年美国匹兹堡艺术学院录取率

    匹兹堡艺术学院成立于1921年,为了适应当时的社会环境应运而生,起初以广告商业学为主导课程,后来经过不断发展,逐渐增开了其他课程,可授予学士学位、副学士学位,除了专业课的学习外,还开设一般通识课程,与

    2022-07-07
    000
  • 伦敦玛丽女王大学学条件

    伦敦玛丽女王大学(Queen Mary University of London,简称QM)以英国玛丽王后命名,又译伦敦大学玛丽女王学院, 世界百强名校,英国常春藤名校联盟“罗素大学集团”成员,英联邦

    2022-07-07
    300
  • 西雅图城市大学最新申请条件怎么样

      西雅图城市大学最新申请条件怎么样?最新西雅图城市大学申请条件,具体请咨询立思辰留学360美国留学顾问,热线电话:4008-941-360院校介绍美国西雅图城市大学(City University

    2022-07-07
    000
  • 2017年美国纽黑文大学奖学金申请

    纽黑文大学是一个以学生为中心强调优秀文学和专业教育的综合性大学,使命是能让学生通过我们提供的高质量的教育和在协作以及基础学习中得到的经验,在全球性的社会生活中能有目的而且比较充实的生活做好准备。立思辰

    2022-07-07
    000
  • 泰国国立发展行政学院学费怎样

    泰国国立发展行政学院立思辰留学360介绍,泰国国立发展行政学院(NIDA)位于泰国首都曼谷,隶属于国家教育部高等教育委员会,建校与1966年4月1日。其前身是泰国Thammasat大学的公共

    2022-07-07
    000
  • 泰国皇太后大学的官网介绍

      泰国清莱皇太后大学立思辰留学360介绍,皇太后大学于1998年9月25日正式成立,她是一所国立自治大学。她的建立是为了回应泰国北方人民为缅怀诗娜卡琳皇太后殿下宏恩厚泽的需要,使之成为人民纪念、效忠

    2022-07-07
    000
  • 朱拉隆功大学学校特色

    泰国朱拉隆功大学于1917年由拉玛六世捐赠校地而创立,并赐予父亲拉玛五世的名字作为校名。朱拉为泰国第一所创立的高等教育机构,从拉玛七世开始,每年由国王亲自在毕业典礼颁发证书。现任国王拉玛九世蒲美蓬因身

  • 新加坡TMC学院本科课程有哪些

    新加坡TMC学院自1981年成立以来,本着为本地和国际学生提供高品质教育的理念,从最初一间培训机构不断壮大,现在已经拥有商学院、信息科技学院、人文学院、酒店旅游和烹饪学院、心理学学院、宏敦语言中心、剑

    2022-07-07
    000

发表评论

登录后才能评论

评论列表(0条)

    保存