关于java:LeetCode刷题日记之反转链表

明天来看一道简略然而比拟常考的题,题的解法是很简略的,递归代码的话硬背都能记住,但真的把代码逻辑理清的人不是很多。我心愿你看完看完这篇文章之后能把递归和迭代的思路整个理分明,代码为什么会那么写,从而解脱背的窘境。

先看下题:

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输出:head = [1,2,3,4,5]
输入:[5,4,3,2,1]

递归

咱们先来看看递归解法,递归首先是找递归终止条件,这里咱们假设是原函数就是递归调用函数,原函数是须要返回一个ListNode,所以比拟天然的想到当递归函数传的ListNode为null或者下一个指针为null时退出以后层,代码如下:

        if (head == null || head.next == null) {
            return head;
        }

而后咱们定义一个节点P示意head.next的翻转后果。

        ListNode p = reverseList(head.next);

简略解释下,在没有执行reverseList(head.next)之前链表是1->2->3->4->5;当执行该函数之后,因为会进行递归调用,直到最初一个节点,所以节点p的指向为5->4->3->2->null;这时候整个链表的指向为1->2<-3<-4<-5;

它离咱们最初的指标null<-1<-2<-3<-4<-5是不是很靠近了?咱们只须要将最初一步2指向1,并且将1指向Null就能够。

留神这里不能用p.next指向head,而应该用head.next指向head。因为p指的是以5结尾的节点,它的next是4,这样指的话会使4前面节点全副断掉。初学者很容易犯这种谬误,而后指着指着把本人搞晕。咱们这里间接应用head.next示意2,而后把它下一个节点指向1,再把1的下一个节点指向空。这里如果有点搞不清楚的,倡议翻一下我后面k个一组翻转链表那篇文章里写的做链表题的一些常识,你就会清晰很多。于是有了上面代码:

        head.next.next = head;
        head.next = null;

那最初咱们应该返回的后果时什么呢?head.next么?不是的,是p。这时候p是从5开始指向1的残缺链表。

整合下递归的残缺代码如下:

        if (head == null || head.next == null) {
            return head;
        }

        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return p;

当然,这么说你可能还是对reverseList(head.next)这个函数的具体流程很纳闷,我一开始也是这样,这个可能须要你对递归有肯定熟练程度之后能力有概念。

你能够这么思考,当head==null||head.next==null时,就会跳出以后层,否则会始终往下走。

这里第一次跳进去是head.next值为5的时候,而后它会做什么呢?head.next.next=head这层栈调用的head参数是4,因而会将head.next指向head,就是5指向4,而后将4指向null。

这时候的链表形态是1->2->3->4<-5这样的。p的形态是5->4->null

而后会返回p到上一层栈函数,上一层的head是3,head.next是4,执行head.next.next = head;head.next = null这两行代码之后整个链表形态是1->2->3<-4<-5。p的形态是5->4->3->null

而后在返回p,反复上述过程,最初在以后函数失去1->2<-3<-4<-5这样的p,通过最初两行代码反转之后失去整个反转之后的链表。

你依照我这个思路过两次,应该就大略晓得这个题的递归流程了。

这个画了一个示意图,你能够大略参考下,和下面思路对应,你能够对照着看:

迭代

接下来看看迭代的代码:

迭代的整个思路绝对递归简略很多,就是结构一个prev指针和一个curr指针,一开始prev指针为null,curr指针为head,一直用curr指向prev,做过这步后顺次将prev和curr后移,一直反复上述过程,直到curr为null,而后这时候的prev就是翻转后的链表。

具体代码如下:

        ListNode pre = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            //1->2变成1<-2,反转链表
            curr.next = pre;
            //将curr和next像后移
            pre = curr;
            curr = next;
        }
        return pre;

while外面的代码大略说一下,因为curr.next在第二步会断掉,前面又会用到curr.next,因而提前结构一个next指针指向curr.next,这样在前面指针后移的时候不会出错。

具体过程你能够看上面这个示意图:

下面的代码其实还能够优化,curr这个变量其实没什么用,咱们能够间接用head代表curr。代码如下:

        ListNode newHead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;

然而理论工程中不太倡议应用下面这种写法,因为它会扭转原始数据,如果传得这个参数是一个公共数据,有多个中央应用,你批改了这个数据会对其余模块也造成影响,所以比拟倡议用第一种写法。但如果你能必定没有其余中央会应用这个数据的话,第二种写法也是能够的。

写在最初

链表绝对于数组会难了解点,特地是老手,一开始链表指着指着就懵了,最初不晓得指到哪里去了。我一开始学也是这样,看链表题解法感觉就和看天书一样,但只有你长时间做题,重复回顾,把链表代码里一些套路(也能够说是常识)弄明确之后,再去了解就会清晰很多。

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据