问题描述

92，反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

先实现用于反转单链表的辅助函数 reverse(linked_list)。

从头节点向后走 m - 1 步，找到 m 对应的节点 p1，以及 p1 的前一个节点 p1_prev（当 m 等于 1 时，p1_prev 是 NULL），然后再走 n - m 步，找到 n 对应的节点 p2。

将列表分成三段：

• left：head -> ... -> p1_prev
• middle：p1 -> ... -> p2
• right：p2.next -> ... -> NULL

并且当 p1_prev 是 NULL 时，left 为 NULL。

使用 reverse() 方法对 middle 进行反转，然后再将这三段接起来，即可得到最终结果。

Python 实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    @staticmethod
    def print_linked_list(head):
        temp = head
        while temp is not None:
            print(temp.val)
            temp = temp.next

    def reverse(self, linked_list):
        if linked_list is None or linked_list.next is None:
            return linked_list

        p1 = linked_list
        p2 = linked_list.next
        p1.next = None
        while p2 is not None:
            p2_next = p2.next
            p2.next = p1
            p1 = p2
            p2 = p2_next
        return p1

    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if head is None or head.next is None or m == n:
            return head

        p1 = head
        p1_prev = None
        for _ in range(m - 1):
            p1_prev = p1
            p1 = p1.next

        if p1_prev is None:
            left = None
            left_last = None
        else:
            left = head
            left_last = p1_prev
            p1_prev.next = None

        p2 = p1
        for _ in range(n - m):
            p2 = p2.next

        right = p2.next
        p2.next = None

        middle = self.reverse(p1)
        middle_last = p1

        if left is None:
            middle_last.next = right
            return middle

        left_last.next = middle
        middle_last.next = right
        return left