反转链表(系列)

python3

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

# 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

Golang

C

C++

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

复用以前的反转算法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # head为第一个要处理的节点，tail为要处理节点的下一个节点，可能为None
        def reverseList(head, tail):
            prev = tail
            cur = head
            p = head
            while p != tail:
                p = p.next
                cur.next = prev
                prev = cur
                cur = p
            return prev

        dummy = ListNode(next=head)
        p = dummy
        count = 0
        prev_node = dummy
        right_node = None
        while p:
            if count == left-1:
                prev_node = p
            if count == right:
                right_node = p
                break
            p = p.next
            count += 1
        # print(prev_node.val, right_node.val)
        if not right_node:
            prev_node.next = reverseList(prev_node.next, None)
        else:
            prev_node.next = reverseList(prev_node.next, right_node.next)
        return dummy.next