92 反转链表II

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

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

示例:

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

解法

• 创建新的列表，将列表中的m到n反转，然后输出链表。时间空间复杂度均为O(n)

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

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        ls = []
        cur = head
        while cur:
            ls.append(cur.val)
            cur = cur.next
        ls = ls[:m-1]+ls[m-1:n][::-1]+ls[n:]
        cur = head
        for i in ls:
            node = ListNode(i)
            cur.next = node
            cur = cur.next
        return head.next

• 双指针，时间复杂度O(n)，空间复杂度O(1)。

    m           n
1-> 2-> 3-> 4-> 5-> 6-> NULL
|   |           |   |
a   b           c   d 
    |           |
    -------------
      反转该段链表

记录a,b,c,d段结点，a.next = c, d.next = d

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if (head == None) or (head.next == None) or (m==n):
            return head
        dummy = ListNode(-1)
        dummy.next = head
        a,d = dummy,dummy
        for _ in range(m-1):
            a = a.next
        for _ in range(n):
            d = d.next
        b,c = a.next,d.next
        pre = b
        cur = pre.next
        while cur!=c:
            cur.next,pre,cur = pre,cur,cur.next
        a.next = d
        b.next = c
        return dummy.next