206.反转链表.py

#
# @lc app=leetcode.cn id=206 lang=python3
#
# [206] 反转链表
#
# https://leetcode-cn.com/problems/reverse-linked-list/description/
#
# algorithms
# Easy (68.38%)
# Likes:    892
# Dislikes: 0
# Total Accepted:    210.3K
# Total Submissions: 307.5K
# Testcase Example:  '[1,2,3,4,5]'
#
# 反转一个单链表。
# 
# 示例:
# 
# 输入: 1->2->3->4->5->NULL
# 输出: 5->4->3->2->1->NULL
# 
# 进阶:
# 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
# 
#

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class ListNode():
    def __init__(self, val):
        if isinstance(val,int):
            self.val = val
            self.next = None
            
        elif isinstance(val,list):
            self.val = val[0]
            self.next = None
            cur = self
            for i in val[1:]:
                cur.next = ListNode(i)
                cur = cur.next
    
    def gatherAttrs(self):
        return ", ".join("{}: {}".format(k, getattr(self, k)) for k in self.__dict__.keys())

    def __str__(self):
            return self.__class__.__name__+" {"+"{}".format(self.gatherAttrs())+"}"
from functools import lru_cache
class Solution:
    def iteration(self, head: ListNode):
        # 迭代！！
        p, rev = head, None
        while p:
            # rev, rev.next, p = p, rev, p.next
            rev = p
            rev.next = rev
            p = p.next
        return rev
    def tree(self, head):
        while head:
            print(head.val)
            head = head.next
            
    def recursion(self, head:ListNode):
        if not head or not head.next:
            return head
        rev = self.recursion(head.next)
        self.tree(head)
        head.next.next = head
        head.next = None
        return rev

    def reverseList(self, head: ListNode) -> ListNode:
        # 迭代！！
        return self.recursion     (head)

# @lc code=end
if __name__ == "__main__":
    test = Solution()
    print(test.reverseList(ListNode([1,2,3,4,5])))