LeetCode 92. Reverse Linked List II

November 18, 2024

I was able to reduce this time complexity from O(n) = 2n to O(n) = n by using a list for the elements to be reversed, and then only modifying those rather than stepping through all nodes while reversing.

Solution

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
8        first = head
9        start = None
10        end = None
11        last = None
12        toReverse = []
13        i = 0
14        while i < right:
15            if i == max(left - 2, 0):
16                start = head
17            if i == right - 1:
18                end = head
19            if i >= left - 1 and i < right - 1:
20                toReverse.append(head)
21            head = head.next
22            i += 1
23        
24        last = end.next
25        if left > 1:
26            start.next = end
27            start = start.next
28        else:
29            start = end
30            first = start
31        head = start
32        while toReverse:
33            head.next = toReverse.pop()
34            head = head.next
35        if head.next:
36            head.next = last
37
38        return first

LeetCode 138. Copy List with Random Pointer

LeetCode 25. Reverse Nodes in k-Group