reverse sublist
Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 m n length of list.
Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL
Reversing a sublist in one pass is a notoriously hard problem. It requires meticulous and painstaking pointer work.
Solution
The first step is to create a dummy head, and a pointer P
to the node before the head of the sublist.
Next, a tail pointer is created, pointing to the node after the head 'P'.
Do notice that the tail
pointer doesn't move, rather it points to the next node after the sublist. Do also notice that P
always points to the start of the sublist.
For this rewiring to take place, a tmp
variable is used to iterate over the nodes that need changing.
The tmp
variable acts as an iterator of sorts, it's the main point of interest during the iteration. During the iteration we:
- connect the
tail
totmp
's next. - connect
tmp
toP
's next. - connect
P
's next totmp
.
The pattern is tail
, tmp
, p
. This graphic will help you remember this pattern visually.
1def reverse_sublist(L, start, finish):
2 dummy = P = ListNode(0, L)
3 for _ in range(1, start):
4 P = P.next
5
6 tail = P.next
7 for _ in range(finish - start):
8 tmp = tail.next
9 tail.next, tmp.next, P.next = (tmp.next, sub.next, tmp)
10 return dummy.next
Time and Space Complexity