2022-02-08单链表反转-3种链表操作方法

方法一：依次插入空头节点后完成反转

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 1.构造带头节点的空链表，注意next为None，后续会变为最后一个节点
# 2. 将链表节点p依次插入空链表的头节点之后
# 3. 注意终止条件，q=NULL
# 4. 注意处理最后一个p节点
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        dummy = ListNode(0)

        p = head
        q = head.next
        while q:
            p.next = dummy.next
            dummy.next = p
            p = q
            q = q.next
        p.next = dummy.next
        dummy.next = p
        return dummy.next

方法二：直接链表一次遍历完成反转

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# pre初始指向空，p指向当前待处理节点，初始为head，q记录p的下一个节点
# p连上上一个节点pre，pre变为当前节点p，p后移指向下一个待处理节点q
# 结束时，p为空，pre为最后被处理的节点，即新链表的头节点
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        pre = None
        p = head
        while p:
            q = p.next
            p.next = pre
            pre = p 
            p = q
        return pre

方法三：迭代求解

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 以第一个节点为未反转部分，剩下部分为已求解部分
# 第二个节点为已求解部分最后的一个节点，将最后一个未反转节点加入已求解部分
# 注意两点：1. head.next为空需要提前判断，否则有语法错误   2.最终一个节点的next为None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        right = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return right