Leetcode 92

Posted on | | 阅读数
Words count in article: 206 | Reading time ≈ 1

Question

Solution1

因为是单向链表，所以可以考虑将链表转换为列表，进行排序后，在转换为链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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:
        if m == n:
            return head
        temp = []
        ans = cur = head
        while cur:
            temp.append(cur.val)
            cur = cur.next
        temp = temp[:m-1] + temp[m-1:n][::-1] + temp[n:]
        head.val = temp[0]
        for i in range(1, len(temp)):
            nn = ListNode(temp[i])
            head.next = nn
            head = head.next
        return ans

Solution2

只用链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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:
        if m == n:
            return head
        ans = pre = ListNode(0)
        pre.next = head
        for i in range(m - 1):
            pre = pre.next
        cur = pre.next
        reverse = None
        for i in range(n-m+1):
            next = cur.next
            cur.next = reverse
            reverse = cur
            cur = next
        nn = pre.next
        pre.next = reverse
        nn.next = cur
        
        return ans.next