有关心情

题目描述：
反转一个单链表。

示例:

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

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

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

第一种：利用栈先进后出的特点，把链表中的结点顺序压进去。然后依次弹出来，构建新的链表，实现反转效果。

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    """
    执行用时: 84 ms, 在Reverse Linked List的Python3提交中击败了5.02% 的用户
    内存消耗: 7.9 MB, 在Reverse Linked List的Python3提交中击败了97.17% 的用户
    """
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        stack = [None]
        cur = head
        while cur:
            stack.append(cur)
            cur = cur.next

        newHead = stack.pop()
        p = newHead
        while stack:  # 构建新链表
            p.next = stack.pop()
            p = p.next

        return newHead

第二种：迭代

class Solution:
    """
    执行用时: 48 ms, 在Reverse Linked List的Python3提交中击败了99.79% 的用户
    内存消耗: 7.9 MB, 在Reverse Linked List的Python3提交中击败了98.02% 的用户
    """
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre, cur = None, head
        while cur:
            cur.next, cur, pre = pre, cur.next, cur
        return pre

为便于理解，对while中的代码扩展如下，实现思路在注释中：

while cur:
    next = cur.next  # 用指针指向下一个元素
    #（为方便理解，这里的cur.next表示下个元素）

    cur.next = pre  # 将这个箭头指向上一个元素
    # （此时的cur.next表示两个链表元素之间的箭头）
    pre = cur  # 前驱指针向后移动一个元素
    cur = next  # 当前指针向后移动一个元素

第三种：递归

class Solution:
    """
    执行用时: 56 ms, 在Reverse Linked List的Python3提交中击败了49.41% 的用户
    内存消耗: 12.5 MB, 在Reverse Linked List的Python3提交中击败了5.38% 的用户
    """
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if head is None or head.next is None:
            return head

        # 当self.reverseList()返回时，afterHead指到了链表的最后一个结点
        # 如果认为afterHead为当前结点，那么head表示上个结点
        afterHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return afterHead  # 总是指向反转后的链表头

递归详情可见：https://blog.csdn.net/FX677588/article/details/72357389