Reverse Linked List

Approach

initialization_phase:

1. Initialize prev to None to represent the fact that the first node in the reversed linked list has no previous node.
2. Initialize curr to head to represent the fact that we will start processing nodes at the head of the original linked list.

maintenance_phase:

1. In each iteration of the loop, we first store a reference to the next attribute of curr in the next_node variable. This is done to ensure that we don’t lose the reference to the next node in the original linked list when we modify the next attribute of curr.
2. We then set the next attribute of curr to prev, effectively reversing the direction of the next pointer of curr.swap_elements
3. We update prev to be curr, so that it points to the current node in the reversed linked list.
4. We update curr to be next_node, so that it points to the next node in the original linked list.

termination_phase:

1. The loop terminates when curr becomes None. This happens when we have processed all nodes in the original linked list.
2. At this point, prev points to the last node in the original linked list, which is now the first node in the reversed linked list. Therefore, we return prev.

• Tip: In Python null is represented by None.

Code

class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
 
def reverse_linked_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev, curr = curr, next_node
    return prev
 
 
head = Node(1, Node(2, Node(3, Node(4, Node(5)))))
 
result = reverse_linked_list(head)
 
# Print the reversed linked list
while result:
    print(result.val)
    result = result.next
 

Attempt ✅

optimise_code

• Had missed adding variable declaration, adding let increased the memory and reduced the runtime.
• Add edge case if head is null return head or return null.

'''
#gyan_pelo 
to reverse a linked list change the pointer or the next to the previous element
have two elements at a time in the #maintaince_phase scope and change the next pointer to previous
use only a temporary variable if required, don't store the values in another array or linked list or stack because than it will not be #in_place 
 
'''
 

/**
gyan pelo:
To reverse the linked list the pointers have to be flipped. Store the current node value then override it. Also last node needs to point to null so at starting of loop handle that. Previous should have the updated linked list.
**/
class Node {
	value;
	next;
 
	constructor(value, next) {
		this.value = value;
		this.next = next;
	}
}
 
function reverseLinkedList(head) {
	previous = null;
	current = head;
 
	while (current != null) {
		next_value = current.next;
		current.next = previous;
		[previous, current] = [current, next_value]
	}
	return previous;
 
}
 
var head = new Node(1, new Node(2, new Node(3, new Node(4, new Node(5))))) 
result = reverse_linked_list(head);