LeetCode 206：反转链表 Reverse Linked List

Gilbertat 发布于2019-08-16 18:39 / 3489人阅读

摘要：反转一个单链表。示例输入输出进阶你可以迭代或递归地反转链表。你能否用两种方法解决这道题解题思路每次遍历到最后一位取节点这种方法就算了时间复杂度太高。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。

反转一个单链表。

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

云服务器 GPU云服务器 python反转链表 linked 服务器206 Reverse

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/75516.html

LeetCode 之 JavaScript 解答第206题 —— 反转链表（Reverse Link

摘要：算法思路两种方法一般反转递归法一般解决定义三个指针，分别为，存储当前结点，指向反转好的结点的头结点，存储下一结点信息。递归法重点分析先确定终止条件当下一结点为时，返回当前节点判断当前的链表是否为递归找到尾结点，将其存储为头结点。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿题目：Reverse...

zhangfaliang 2019-08-23 17:12 评论0 收藏0
LeetCode 206：反转链表 Reverse Linked List

摘要：反转一个单链表。示例输入输出进阶你可以迭代或递归地反转链表。你能否用两种方法解决这道题解题思路每次遍历到最后一位取节点这种方法就算了时间复杂度太高。从链表末尾向头部逐个分离节点，并将节点添加到新链表的末尾。与迭代法原理相似。反转一个单链表。 Reverse a singly linked list. 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2...

heartFollower 2019-07-31 11:29 评论0 收藏0
LeetCode 234：回文链表 Palindrome Linked List

摘要：请判断一个链表是否为回文链表。然后是判断是否是回文链表不考虑进阶要求的话，方法千千万。好在这道题只要求返回布尔值，即便把原链表改变了也不用担心。然后从原链表头节点与反转后后半部分链表头节点开始对比值即可。请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->...

luqiuwen 2019-08-16 18:41 评论0 收藏0
LeetCode 234：回文链表 Palindrome Linked List

摘要：请判断一个链表是否为回文链表。然后是判断是否是回文链表不考虑进阶要求的话，方法千千万。好在这道题只要求返回布尔值，即便把原链表改变了也不用担心。然后从原链表头节点与反转后后半部分链表头节点开始对比值即可。请判断一个链表是否为回文链表。 Given a singly linked list, determine if it is a palindrome. 示例 1: 输入: 1->...

hlcc 2019-07-31 11:30 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0