题解 | #反转链表#

class Solution:
    def ReverseList(self, head: ListNode) -> ListNode:
        # MOST EASY SOLUTION BUT O(n) IN SPACE
        # stack = []
        # while head:
        #     stack.append(head.val)
        #     head = head.next
        # res = cur = ListNode(0)
        # while stack:
        #     cur.next = ListNode(stack.pop())
        #     cur = cur.next
        # return res.next

        # BELOW IS A SOLUTION TAKE O(1) IN SPACE
        # THE POINTER BETWEEN pre AND cur is the loop, IT SHOULD BE NOT BE LINKED
        pre = None
        cur = head
        while cur:
            tmp = cur.next
            cur.next = pre
            pre, cur = cur, tmp
        return pre