DSA question

[yasaduni]

How to reverse a linked list?

[suba7312]

Reversing a linked list is a common problem in data structures Steps to Reverse a Linked List Initialize Three Pointers:

prev: This will eventually become the new head of the reversed list. Initially, it is set to None. current: This points to the current node being processed. Initially, it is set to the head of the linked list. next_node: This temporarily stores the next node before changing the current node's next pointer. Iterate Through the List:

Loop through the list, and at each step, reverse the next pointer of the current node to point to the prev node. Move the prev and current pointers one step forward. Update the Head:

After the loop, the prev pointer will be at the new head of the reversed list. Python Implementation Here's how you can implement this in Python:

python Copy code class ListNode: def init(self, value=0, next=None): self.value = value self.next = next

def reverse_linked_list(head): prev = None current = head

while current:
    next_node = current.next  # Store the next node
    current.next = prev  # Reverse the current node's pointer
    prev = current  # Move prev and current one step forward
    current = next_node

return prev  # prev will be the new head of the reversed list

Helper function to print the linked list (for testing purposes)

def print_linked_list(head): current = head while current: print(current.value, end=" -> ") current = current.next print("None")

Example usage

Creating a linked list: 1 -> 2 -> 3 -> 4 -> None

head = ListNode(1) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(4)

print("Original Linked List:") print_linked_list(head)

Reverse the linked list

reversed_head = reverse_linked_list(head)

print("Reversed Linked List:") print_linked_list(reversed_head) Explanation of the Code: ListNode Class: Defines a node in the linked list with a value and a next pointer.

reverse_linked_list Function:

prev is initially set to None because the new tail of the reversed list (the original head) should point to None. current starts at the head of the list. The while loop continues until all nodes have been reversed. print_linked_list Function: A helper function to visualize the linked list before and after reversal.

Output: Running the example code will produce:

Original Linked List: 1 -> 2 -> 3 -> 4 -> None Reversed Linked List: 4 -> 3 -> 2 -> 1 -> None

[sofde]

Above solution is correct

[ektaa1]

Here is a direct solution in C++

// Iterative C++ program to reverse a linked list

include

using namespace std;

class Node { public: int data; Node* next;

Node(int new_data) {
    data = new_data;
    next = nullptr;
}

};

// Given the head of a list, reverse the list and return the // head of reversed list Node reverseList(Node head) {

  // Initialize three pointers: curr, prev and next
Node *curr = head, *prev = nullptr, *next;

  // Traverse all the nodes of Linked List
while (curr != nullptr) {

    // Store next
    next = curr->next;

    // Reverse current node's next pointer
    curr->next = prev;

    // Move pointers one position ahead
    prev = curr;
    curr = next;
}

  // Return the head of reversed linked list
return prev;

}

void printList(Node* node) { while (node != nullptr) { cout << " " << node->data; node = node->next; } }

int main() {

// Create a hard-coded linked list:
// 1 -> 2 -> 3 -> 4 -> 5
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);

cout << "Given Linked list:";
printList(head);

head = reverseList(head);

cout << "\nReversed Linked List:";
printList(head);

return 0;

}