I'm doing a bootcamp of DS&A and there is an exercise of reversing certain elements from a linked list but I don't understand the code and the explanation given wasn't clear enough.
This is the linked list:
linked_list = LinkedList(1)
linked_list.append(2)
linked_list.append(3)
linked_list.append(4)
linked_list.append(5)
Method:
def reverse_between(self, start_index, end_index):
if self.length <= 1:
return
dummy_node = Node(0)
dummy_node.next = self.head
previous_node = dummy_node
for i in range(start_index):
previous_node = previous_node.next
current_node = previous_node.next
for _ in range(end_index - start_index):
node_to_move = current_node.next
current_node.next = node_to_move.next
node_to_move.next = previous_node.next
previous_node.next = node_to_move
self.head = dummy_node.next
I don't understand what the first loop is doing. As far as I am concerned, the previous_node before the loop is already pointing to the dummy_node (0) which is at the start of the LL but not the head. Then in the for loop, assuming that the start_index is "2", then the previous node updates twice, moving then to the first node and then to the second node in the LL which would be the one with a value of 2.
The code with comments says the following:
# 4. Move 'previous_node' to its position.
# It'll be at index 'start_index - 1' after this loop.
for i in range(start_index):
previous_node = previous_node.next
So instead of being in the second node, it is in the node before which would be the 1. What am I missing here?
I'm providing here the full code with comments.
def reverse_between(self, start_index, end_index):
# 1. Edge Case: If list has only one node or none, exit.
if self.length <= 1:
return
# 2. Create a dummy node to simplify head operations.
dummy_node = Node(0)
dummy_node.next = self.head
# 3. Init 'previous_node', pointing just before reverse starts.
previous_node = dummy_node
# 4. Move 'previous_node' to its position.
# It'll be at index 'start_index - 1' after this loop.
for i in range(start_index):
previous_node = previous_node.next
# 5. Init 'current_node' at 'start_index', start of reversal.
current_node = previous_node.next
# 6. Begin reversal:
# Loop reverses nodes between 'start_index' and 'end_index'.
for i in range(end_index - start_index):
# 6.1. 'node_to_move' is next node we want to reverse.
node_to_move = current_node.next
# 6.2. Disconnect 'node_to_move', point 'current_node' after it.
current_node.next = node_to_move.next
# 6.3. Insert 'node_to_move' at new position after 'previous_node'.
node_to_move.next = previous_node.next
# 6.4. Link 'previous_node' to 'node_to_move'.
previous_node.next = node_to_move
# 7. Update list head if 'start_index' was 0.
self.head = dummy_node.next
You write:
So instead of being in the second node, it is in the node before which would be the 1. What am I missing here?
That analysis is correct. I'm not sure what you think you are missing, but a general principle in manipulating linked lists is that you need a reference to the node that precedes the first node that needs to be rearranged.
It may help to visualise the process with an example call on your linked list with 5 nodes.
When the reverse_between(linked_list, 2, 3) method is called, we have this state at the very start of that function:
self linked_list
│ │
┌─┴──────┴──┐
│ length: 5 │
│ head: ┐ │
└───────│───┘
┌───┴─────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ──────┤ next: ──────┤ next: Ø │
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
When dummy is created and previous_node gets to reference that same node we get this:
self linked_list
│ │
┌─┴──────┴──┐
│ length: 5 │
│ head: ┐ │
└───────│───┘
┌───┴─────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ──────┤ next: ──────┤ next: Ø │
└───────┬─┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
┌─────────┐ │
│ val: 0 │ │
│ next: ────┘
└─┬─────┬─┘
│ │
dummy │
previous_node
Then the first loop starts. As start_index is 2 in this example, the loop will iterate two times, meaning that previous_node will first take on the next reference found in the dummy node, so it references the node with value 1, and (in the second iteration) will follow the next reference found in that node, and so reference the node with value 2 (this is what you had correctly analysed). current_node gets to reference the node after that one:
self linked_list
│ │
┌─┴──────┴──┐
│ length: 5 │
│ head: ┐ │ previous_node current
└───────│───┘ │ │
┌───┴─────┐ ┌────┴────┐ ┌────┴────┐ ┌─────────┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ──────┤ next: ──────┤ next: Ø │
└───────┬─┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
┌─────────┐ │
│ val: 0 │ │
│ next: ────┘
└─┬───────┘
│
dummy
If we assume end_index is 3, the second loop will just make one iteration, with the goal to swap the nodes with values 3 and 4 (as they are at index 2 and 3 of the linked list).
First node_to_move gets to reference the node with value 4.
With current_node.next = node_to_move.next the node with value 4 is "taken out" of the linked list, so we get this:
self linked_list
│ │
┌─┴──────┴──┐
│ length: 5 │
│ head: ┐ │ previous_node current node_to_move
└───────│───┘ │ │ │
┌───┴─────┐ ┌────┴────┐ ┌────┴────┐ ┌─────┴───┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 4 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ────┐ │ next: ──────┤ next: Ø │
└───────┬─┘ └─────────┘ └─────────┘ │ └─────────┘ └──┬──────┘
┌─────────┐ │ └──────────────────┘
│ val: 0 │ │
│ next: ────┘
└─┬───────┘
│
dummy
Then node_to_move.next = previous_node.next places the node with value 4 to come before the node with value 3, although it still is outside of the list (not reachable from the head):
self linked_list node_to_move
│ │ ┌─────┴───┐
┌─┴──────┴──┐ │ val: 4 │
│ length: 5 │ │ next: ┐ │
│ head: ┐ │ previous_node current └───────│─┘
└───────│───┘ │ │ ┌─────────────┘
┌───┴─────┐ ┌────┴────┐ ┌────┴─┴──┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 3 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ────────────────────┤ next: Ø │
└───────┬─┘ └─────────┘ └─────────┘ └─────────┘
┌─────────┐ │
│ val: 0 │ │
│ next: ────┘
└─┬───────┘
│
dummy
And the last statement in the loop inserts node 4 back into the list: previous_node.next = node_to_move
self linked_list node_to_move
│ │ ┌─────┴───┐
┌─┴──────┴──┐ │ val: 4 │
│ length: 5 │ ┌─────────────┤ next: ┐ │
│ head: ┐ │ previous_node │ current └───────│─┘
└───────│───┘ │ │ │ ┌─────────────┘
┌───┴─────┐ ┌────┴────┐ │┌────┴─┴──┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ ││ val: 3 │ │ val: 5 │
│ next: ──────┤ next: ─────┘│ next: ────────────────────┤ next: Ø │
└───────┬─┘ └─────────┘ └─────────┘ └─────────┘
┌─────────┐ │
│ val: 0 │ │
│ next: ────┘
└─┬───────┘
│
dummy
Note that the above mutation shows how important it was to have a reference to the node that precedes the nodes we wanted to rearrange, otherwise we would not have been able to inject the node with value 4 to come after the node with value 2.
And now the rewiring is complete. That last statement of the function is only really necessary if the first node (with value 1) had taken part in the reversal so that it would no longer be the first. In that case previous_node would have the dummy node as reference and head would need to be updated to reference whatever node came after the dummy one. In this example self.head = dummy_node.next doesn't change anything because the first node was not part of the reversal. If we rearrange the above visualisation, we get:
self linked_list
│ │
┌─┴──────┴──┐
│ length: 5 │
│ head: ┐ │ previous_node node_to_move current
└───────│───┘ │ │ │
┌───┴─────┐ ┌────┴────┐ ┌────┴────┐ ┌────┴────┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │ │ val: 3 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ──────┤ next: ──────┤ next: Ø │
└───────┬─┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
┌─────────┐ │
│ val: 0 │ │
│ next: ────┘
└─┬───────┘
│
dummy
After the function returns, the local variables are out of scope and any nodes that become unreachable are discarded: this is the case for the dummy node with value 0:
linked_list
│
┌────────┴──┐
│ length: 5 │
│ head: ┐ │
└───────│───┘
┌───┴─────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │ │ val: 3 │ │ val: 5 │
│ next: ──────┤ next: ──────┤ next: ──────┤ next: ──────┤ next: Ø │
└─────────┘ └─────────┘ └─────────┘ └─────────┘ └─────────┘
Hope this clarifies it.