206. Reverse Linked List

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

solution

• 迭代

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        pre = None
        cur = head
        while cur is not None:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

时间复杂度：O(n) 空间复杂度：O(1)

• 递归

# 从树的角度来看递归
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.recursive(head, None)

    def recursive(self, cur, pre):
        if cur is None:
            return pre

        tmp = cur.next
        cur.next = pre
        return self.recursive(tmp, cur)  # 注意此时的return

时间复杂度：O(n) 空间复杂度：O(n)

follow up

92. Reverse Linked List II

24. Swap Nodes in Pairs

双向链表的反转

class DListNode:
    def __init__(self, val):
        self.val = val
        self.prev = self.next = None

    def reverse(self, head):
        cur = None
        while head:
            cur = head
            head = cur.next
            cur.next = cur.prev
            cur.prev = cur
        return cur