206. 反转链表 [easy]

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

反转一个单链表。

示例:

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

进阶:

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

通过次数272,713 | 提交次数391,420

Third Try

2020-07-09

之前没想到还有这样的迭代版本，属于一次遍历。我之前习惯的都是有尾部指针的写法，但是对于普通链表要找到尾部指针已经遍历了一遍了。其实这个版本才是最符合入门思路的写法，尾部指针的版本没接触过才写不出来。

# 遍历一次的迭代版本
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not (head and head.next):
            return head 
        curr = head
        downstream = head.next 
        curr.next = None # 又忘了这一步进行切断导致无限循环
        while downstream:
            next_ds = downstream.next 
            downstream.next = curr 
            curr = downstream
            downstream = next_ds 
        return curr 

执行用时：24 ms, 在所有 Python提交中击败了74.99%的用户
内存消耗：14.9 MB, 在所有 Python提交中击败了22.73%的用户

Second Try

2020-07-09

递归写法，没写过的话真的很难想到还能这么玩。

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        def reverse(head):
            if not (head and head.next):
                return head
            last = reverse(head.next)
            head.next.next = head 
            head.next = None 
            return last 
        
        return reverse(head)

执行用时：28 ms, 在所有 Python 提交中击败了53.76%的用户
内存消耗：19.3 MB, 在所有 Python 提交中击败了9.09%的用户

First Try

2020-07-07

常规方法，不知道递归方法要怎么实现。。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head 
        node = head 
        while node.next:
            node = node.next 
        tail = node 
        
        while head != tail:
            downstream = tail.next 
            tail.next = head 
            head = head.next 
            tail.next.next = downstream
        return tail 

执行用时：16 ms, 在所有 Python 提交中击败了97.06%的用户
内存消耗：14.7 MB, 在所有 Python 提交中击败了22.73%的用户

206. 反转链表 [easy]​

Third Try​

Second Try​

First Try​

206. 反转链表 [easy]

Third Try

Second Try

First Try