题解 | #反转链表#

反转链表，设置两个指针变量，分别 指向前一个节点 和 当前节点，然后改变指针的next指向。有以下两种方式，两种思路一样，一种迭代的方式，一种是递归的方式。时间复杂度都是O(N)的，空间为O(1)

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:

    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        cur, pre = pHead, None
        while cur:
            cur.next, pre, cur = pre, cur, cur.next # 如果是Java/c++需要引入临时变量
        return pre
    """
    def ReverseList(self, pHead):
        def recur(pre, cur):
            # 递归边界
            if not cur:return pre
            # 递归
            res = recur(cur, cur.next)
            # 回溯
            cur.next = pre
            return res
        return recur(None, pHead)
    """ 

本题的引申题目：给定区间的链表反转。
对于增加难度的反转链表，给定了左右边界，只对内部的子链进行反转。
思路：在本题的基础上，增加子链前后节点的标记；找到子链的左右位置，切断子链在整条链表中的左右连接，然后用本题的方式对子链进行反转；然后用子链前后的标记指针将左中右三部分穿起来。

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def reverse_linked_list(head: ListNode):  # 也可以使用递归反转一个链表
            pre, cur = None, head
            while cur:
                # 将pre->cur转为pre<-cur，然后pre指向cur，cur指向下一个
                cur.next, pre, cur = pre, cur, cur.next

        # 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        for _ in range(left - 1):
            pre = pre.next
        # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
        # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next
        curr = right_node.next

        # 注意：切断链接
        pre.next = None
        right_node.next = None

        # 第 4 步：同第 206 题，反转链表的子区间
        reverse_linked_list(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = curr
        return dummy_node.next