搜索内容

有一个问题?

如果您有任何疑问,可以在下面询问或输入您要寻找的!

leetcode题解206-反转链表

生成海报
Java硬件工程师
Java硬件工程师 2021-02-09 21:42
阅读需:0

难题叙述

翻转一个单链表。

实例:

键入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

解题思路(头插法):

我们要想完成的翻转并不仅是数据信息的挪动,只是牵涉到节点的挪动,因此我们无法应用二维数组。
在这里插入图片描述
大家都了解,头插法获得的链表编码序列与插进的次序恰好反过来,因而我们可以采用那样的方法来处理这个问题。
头插法即每一次将插进的节点插进到链表的第一个部位,例如大家插进1,2,3,4.那麼第1次插进1,第二次将2插进到1的前边,第3次将3插进在2的前边,第4次将4插进3的前边。
1.先界定一个连接点reverseHead =new HeroNode();
2.从头至尾解析xml原先的链表,每解析xml一一个连接点,就将其取下,并放到新的链表reverseHead的最前面.
3.原先的链表的head.next = reverseHead.next

在这里插入图片描述

编码完成:

题中构思比较简单,可是完成起來却随处有坑,时尚博主调节了好长时间才取得成功。

public ListNode reverseList(ListNode head) {
        //假如当今链表为空,或是只有一个节点,不用翻转,立即回到
        if(head==null || head.next==null){
            return head;
        }
        //界定一个輔助的表针(自变量),协助大家解析xml原先的链表
        ListNode cur=head;
        //这一自变量很重要,偏向当今节点的下一个节点,不然你挪走当今节点的情况下,全部链表就断开了
        ListNode next=null;         
        ListNode reverseHead=new ListNode(-1);  //头节点
        reverseHead.next=null;
        //解析xml原先的链表,每解析xml一个节点,就将其取下,并放到新的链表的最前面
        while(cur!=null){
            //最先要保存cur的下边一个节点。由于后边必须应用
            next=cur.next;          
            cur.next=reverseHead.next;  //将cur的下一个节点偏向新的链表最前面
            reverseHead.next=cur;         
            //这里边只有是cur=next,而不可以是cur=cur.next,由于大家早已改动cur.next到新的链表中来到 
            cur=next;           
        }
        return reverseHead.next;
    }

小结:

题中关键环节1:要应用next表针,next表针十分关键,偏向当今节点的下一个节点,不然你挪走当今节点的情况下,全部链表就断开了。在大家开展解析xml的全过程中,大家会让cur.next偏向reverseHead.next,这时cur后边的链就都断掉了,因此大家必须在挪动cur表针以前,储存好cur.next。
题中关键环节2:cur后退不会再是cur=cur.next,只是cur=next,由于大家早已修改过去了cur.next表针了。

评论
  • 消灭零回复