#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# author: bigfoolliu


"""
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 

示例 1：


输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：


输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


import doctest


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


class Solution:
    """
    todo；
    """

    def reverseList(self, head: ListNode) -> ListNode:
        """
        单链表反主要注意：
            - 头尾节点的处理
            - 循环指针导致的循环调用
        """
        prev, cur = None, head
        while cur:
            prev, cur.next, cur = cur, prev, cur.next  # 注意顺序，前后中-->中前后
        return prev  # 返回前

    def reverseList2(self, head: ListNode) -> ListNode:
        """
        通过构建新的链表实现
        """
        cur = None  # 待构建的链表前节点
        while head:
            cur = ListNode(head.val, cur)
            head = head.next
        return cur


if __name__ == '__main__':
    doctest.testmod()
