题解 | #反转链表#

反转链表

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
    
       if (head != null && head.next != null) {
            ListNode ActualNext = head.next;
            ListNode lastNode = ReverseList(head.next);
            head.next = null;
            ActualNext.next =head;
            return lastNode;
        }
        return head;
    }
}

这道题做过无数八次了,但是再看还是会想半天,抓耳挠腮不堪其扰,现在我把思路记下来当做以后的提示总可以了吧!

反转链表:顾名思义就是把正向的指向变成翻过来如:1->2->3 变成 3->2->1,初看应该很简单直接循环把 node 节点保存在 list 中再反向遍历 list 把 node 一个一个的 next 到前一个后面。

这种办法可行但是太过于暴力,时间复杂度太高了。相同的数据进行循环,那能不能用递归来解决呢?

我们是要把下一个 node 变成前一个 node 的父节点,那我们就先在代码里面写下 head.next 获取到下一个节点吧!我们是要最后把 lastnode 节点给返回成父节点的,所以直接进行递归传入 head.next 返回的 node 就是我们的 lastnode 节点,好了往下走我们进行 head.next.next的赋值ActualNext.next =head;在把 head.next = null 断开和后一个节点的联系。这样 1 节点后面就不会是 2了。

完美!!!

#编程算法学习#
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
06-12 10:50
门头沟学院 Java
你的不定积分没加C:我怎么在学院群看到了同样的话
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务