LeetCode | 反转链表

1
from typing import Optional
2

3

4
class ListNode:
5
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
6
        self.val = val
7
        self.next = next
8

9

10
class Solution:
11
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
12
        prev = None
13
        curr = head
14

15
        while curr:
16
            nxt = curr.next
17
            curr.next = prev
18
            prev = curr
19
            curr = nxt
20

21
        return prev

1
def build_list(vals):
2
    dummy = ListNode()
3
    cur = dummy
4
    for v in vals:
5
        cur.next = ListNode(v)
6
        cur = cur.next
7
    return dummy.next
8

9

10
def to_list(head):
11
    res = []
12
    while head:
13
        res.append(head.val)
14
        head = head.next
15
    return res
16

17

18
sol = Solution()
19

20
assert to_list(sol.reverseList(build_list([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
21
assert to_list(sol.reverseList(build_list([1, 2]))) == [2, 1]
22
assert to_list(sol.reverseList(build_list([]))) == []
23
assert to_list(sol.reverseList(build_list([1]))) == [1]
24

25
print("PASS")