反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
"""
input: 1,2,3,4,5,6 (m = 3, n = 5)
output: 1,2,5,4,3,6
注意：需要加pre_head 节点，以处理m=1的情况
"""
if head is None or head.next is None:
return head
pre_head = ListNode(None)
pre_head.next = head
pre = pre_head
for _ in range(m - 1):
pre = pre.next
cur = pre.next
for _ in range(n-m):
tmp = cur.next
cur.next = tmp.next
tmp.next = pre.next
pre.next = tmp
return pre_head.next
"""
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if head is None or head.next is None:
return head
if m == n:
return head
node = ListNode(None)
node.next = head
left_tail = node
cur = head
cnt = 1
while cur:
if cnt == m-1:
left_tail = cur
if cnt == m:
mid_head = cur
mid_tail = cur
if cnt > m:
tmp = cur.next
cur.next = mid_head
mid_head = cur
cur = tmp
else:
cur = cur.next
if cnt == n:
mid_tail.next = cur
left_tail.next = mid_head
break
cnt+=1
return node.next
"""