> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/02_linked_list/206.-reverse-linked-list.md).

# 206. Reverse Linked List

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

## solution

* 迭代

```python
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)

* 递归

```python
# 从树的角度来看递归
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](/mle-interview/01_leetcode/02_linked_list/92.-reverse-linked-list-ii.md)

[24. Swap Nodes in Pairs](/mle-interview/01_leetcode/02_linked_list/24.-swap-nodes-in-pairs.md)

[双向链表的反转](/mle-interview/01_leetcode/02_linked_list/206.-reverse-linked-list.md)

```python
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
```