专栏首页爱写BugLeetCode 206:反转链表 Reverse Linked List
原创

LeetCode 206:反转链表 Reverse Linked List

反转一个单链表。

Reverse a singly linked list.

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:

你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

解题思路:

每次遍历到最后一位取节点这种方法就算了时间复杂度太高。如题目进阶要求的两种方法,迭代和递归:

迭代:

每次分出来一个节点把节点作为头节点添加到新链表上:

原链表:1->2->3->4->5

分离第一个节点作为头节点添加到新链表:1 原链表:2->3->4->5

分离下一个节点作为头节点添加到新链表:2->1 原链表:3->4->5

分离下一个节点作为头节点添加到新链表:3->2->1 原链表:4->5

分离下一个节点作为头节点添加到新链表:4->3->2->1 原链表:5

分离下一个节点作为头节点添加到新链表:5->4->3->2->1 原链表:null

Java:

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = null;
        ListNode tmp = null;
        while (head != null) {
            tmp = head.next;//tmp暂存当前节点的下一个节点
            head.next = pre;//当前节点下一个指向pre
            pre = head;//刷新pre
            head = tmp;//刷新当前节点为tmp
        }
        return pre;
    }
}

Python3:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        pre,tmp=None,None
        while(head):
            tmp=head.next
            head.next=pre
            pre=head
            head=tmp
        return pre

递归:

其实就是用递归完成栈的功能:先进后出

基线条件为遇到空节点(到链表末尾),返回对象为链表的最后一个节点,在递归函数中传递一直不变。从链表末尾向头部逐个分离节点,并将节点添加到新链表的末尾。与迭代法原理相似。

原链表:1->2->3->4->5

递归到最后一层时遇到null节点返回尾节点5

回到上一层递归 分离节点 5 作为新链表的尾节点:5,置空原本5节点,原链表1->2->3->4->null

回到上一层递归 分离节点 4 作为新链表的尾节点:5->4,置空原本4节点,原链表1->2->3->null

回到上一层递归 分离节点 3 作为新链表的尾节点:5->4->3,置空原本3节点,原链表1->2->null

回到上一层递归 分离节点 2 作为新链表的尾节点:5->4->3->2,置空原本2节点,原链表1->null

回到上一层递归 分离节点 1 作为新链表的尾节点:5->4->3->2->1,置空原本1节点,原链表null

Java:

class Solution {
    public ListNode reverseList(ListNode head) {
        //基线条件
        if (head == null || head.next == null) return head;
        //递归
        ListNode tmp = head.next;//暂存头节点的下一个节点
        ListNode pre = reverseList(head.next);//递归调用该函数,pre为返回的新链表的头节点,原链表的最后一个节点,无论递归多少层该返回值一直传递不变
        tmp.next = head;//暂存的下一个节点指向传入节点
        head.next = null;//下一个节点即原本指向tmp的节点 置空
        return pre;
    }
}

Python3:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        tmp = head.next
        pre = self.reverseList(head.next)
        tmp.next = head
        head.next = None
        return pre

欢迎关注公.众号一起刷题:爱写Bug

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • LeetCode 206:反转链表 Reverse Linked List

    A linked list can be reversed either iteratively or recursively. Could you imple...

    爱写bug
  • Java实现单向链表

    一、前言 最近在回顾数据结构与算法,有部分的算法题用到了栈的思想,说起栈又不得不说链表了。数组和链表都是线性存储结构的基础,栈和队列都是线性存储结构的应用~ 本...

    Java3y
  • Java-双向链表-从实现到各类操作(全家桶,包含各类常见方法)

    版权声明:署名,允许他人基于本文进行创作,且必须基于与原先许可协议相同的许可协议分发本文 (Creative Commons)

    Fisherman渔夫
  • Java的ConcurrentLinkedQueue

    实现一个线程安全的队列有两种实现方式一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同...

    用户3467126
  • 精选 TOP 面试题 001 | LeetCode 237. 删除链表中的节点

    请编写一个函数,使其可以删除某个链表中给定的(非末尾)节点,你将只被给定要求被删除的节点。

    江不知
  • JS数据结构第五篇 --- 二叉树和二叉查找树

    从逻辑结构角度来看,前面说的链表、栈、队列都是线性结构;而今天要了解的“二叉树”属于树形结构。

    tandaxia
  • 探索 Apache NIFI 集群的高可用

    前言:本文重点在于通过模拟事故来探索Apache NIFI集群的高可用,情景假定有一个3节点的NIFI集群,其中某个节点因为未知原因与集群失联,研究集群(两个在...

    用户5475193

扫码关注云+社区

领取腾讯云代金券