【LEETCODE】模拟面试-206. Reverse Linked List

图:新生大学

https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

**input: **a single linked list output: a list node head of the reverse list of given input **corner: **when the list is null, or only contains one head

What we want to do is to reverse the list. So we scan from head to tail. For every two nodes cur and cur.next, we will make cur point to its forward node.

So at each step, we need a node pre to keep connection with current scanner, so that cur.next = pre. And we also need a node nextOne to memorize cur.next, since it will be changed during the scanner, if without track, cur will lose its way to next scanner.

In order to move to next scanner, pre will move to cur, and cur will move to nextOne.

Until cur moves to tail null, pre is currently the new head of the reversed list, so just return it.

The idea of Recursion is similar with Iteration, what to do in current scanner is to keep track of nextOne and point to pre, and what to prepare for next step is to pass nextOne and cur as the new 'cur' and 'pre'.

//iteration
public class Solution{
    public ListNode reverseList(ListNode head){
        //corner
        if ( head == null || head.next == null ){
            return head;
        }
        
        ListNode pre = null;
        ListNode cur = head;

        while ( cur != null ){
            //reverse
            ListNode nextOne = cur.next;
            cur.next = pre;
            //prepare
            pre = cur;
            cur = nextOne;
        }
        
        return pre;
    }
}

//recursion
public class Solution{
    public ListNode reverseList(ListNode head){
        //corner
        if ( head == null || head.next == null ){
            return head;
        }
        
        ListNode pre = null;
        
        return helper(head, pre);
    }
    
    public ListNode helper(ListNode cur, ListNode pre){
        //base
        if ( cur == null ){
            return pre;
        }
        
        //current
        ListNode nextOne = cur.next;
        cur.next = pre;
        
        //next
        return helper(nextOne, cur);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏何俊林

FFmpeg总结(十一)用ffmpeg进行转格式,Android下播放网络音频流

图:杭州西湖 思路: 1、mp3转成pcm(音频数据),ffmpeg做的事 2、OpenSL ES引擎创建AudioPlayer,实际调用了AudioTra...

76850
来自专栏zaking's

RFC2616-HTTP1.1-Methods(方法规定部分—单词注释版)

12650
来自专栏分布式系统进阶

Librdkafka的各种task处理

21630
来自专栏WindCoder

Best Programming Editors? A Never Ending Battle With No Clear Winner

原文:Best Programming Editors? A Never Ending Battle With No Clear Winner

7810
来自专栏别先生

一脸懵逼加从入门到绝望学习hadoop之 org.apache.hadoop.ipc.RemoteException(org.apache.hadoop.security.AccessControlE

1:初学hadoop遇到各种错误,这里贴一下,方便以后脑补吧,报错如下: 主要是在window环境下面搞hadoop,而hadoop部署在linux操作系统上面...

289100
来自专栏Golang语言社区

在Go中使用服务对象模式

NOTE: Most of the code and ideas in this post are things I have been experimenti...

11320
来自专栏技术小黑屋

Jar Mismatch! Fix Your Dependencies

There was a requirement of my work. It requires me to integrated my current proj...

10120
来自专栏10km的专栏

Ubuntu16:cmake生成Makefile编译caffe过程(OpenBLAS/CPU+GPU)塈解决nvcc warning:The 'compute_20', 'sm_20'

之前在ubuntu14下实现了Caffe编译(参见去年写的博客 《 Ubuntu14:cmake生成Makefile编译caffe过程(OpenBLAS/CPU...

58580
来自专栏张善友的专栏

SharpForge - Open source SourceForge / CodePlex implementation

SharpForge - Open source SourceForge / CodePlex implementation SharpForge suppo...

217100
来自专栏CodingToDie

Awesome 项目

72650

扫码关注云+社区

领取腾讯云代金券