Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Range inversion specified in the linked list

Problem description

Give you the head pointer to the singly linked list head and two integers left and right, where left <= right. Reverse the list node from position left to position right to return the reversed list.

Example:

Enter: head = [1,2,3,4,5], left = 2, right = 4

Output:,4,3,2,5 [1]

To analyze problems

For linked list related problems, we must first think clearly, understand the order in which the pointer moves.

For this problem, we can solve it by head insertion. In the list inversion, each time we traverse a node, we insert that node at the beginning of the inversion. As shown below:

Specifically, we define three pointer variables pre, cur, and Next.

  1. We start by moving pre before the first node to be reversed, pre->next=left
  2. Then move the pointer cur to the first node to be reversed, cur=left,
  3. We then assign cur->next to the variable next.
  4. Point the next node of cur to the next node of Next, cur-> Next =next-> Next
  5. Then point the next node of Next to the next node of Pre, i.e. next->next=pre-> Next
  6. Then insert next into the head of the list, pre-> Next = Next.
  7. Then repeat 3, 4, 5, and 6 until the list is reversed.

Let’s take a look at how the code works.

class Solution: def reverseBetween(self, head, left, right): Dummynode = ListNode(-1) dummyNode = ListNode(-1) DummyNode = next = head pre = dummyNode Left for _ in range(left-1): Cur = pre. Next for _ in range(right-left): next = cur.next cur.next = next.next next.next = pre.next pre.next = next return dummynode.nextCopy the code

The time complexity of this algorithm is O(N), where N is the total number of nodes in the linked list. After traversing the list at most once, the inversion is complete. The space complexity is O(1), and only constant variables are used.