[数据结构与算法]206.反转链表|迭代|递归

• 迭代

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head : return None
        if not head.next: return head # 特殊情况

        pre = head 
        cur = head.next 
        pre.next = None # 处理第一个结点指向null
        while cur:
            nextnode = cur.next
            cur.next = pre
            # pre.next = None
            pre = cur
            cur = nextnode

        return pre

看了下参考链接：【反转链表】：双指针，递归，妖魔化的双指针

可以将前面的情况合并写：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur = head
        pre = None
        while cur:
            nextnode = cur.next
            cur.next = pre
            pre = cur
            cur = nextnode

        return pre

• 递归，比较难想，看的参考链接

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next : return head
        # not head 是怕整个链表就是空的，返回空；
        # 除了这个情况就是not head.next，这说明head是最后一个结点

        res = self.reverseList(head.next)
        # 假设head是倒数第二个结点
        head.next.next = head 
        # 将最后一个结点的next指针指向倒数第二个结点
        head.next = None 
        # 倒数第二个结点的next指针指向None.
        # 如果这个head不是链表的头指针，则该赋值语句不起作用，因为head.next会在下一个出栈过程中的head.next.next=head（此时的head.next就是之前的head）修改掉【不对！有作用！如果不修改，链表会有环出现】{看图之后发现，emmm好像在这里出现环也没什么大事噢}。 
        # 这句话主要是处理链表的头指针，将其next指针指向None。
        return res

根据代码写的具体过程：