The Gateway to Computer Science Excellence

0 votes

Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that needed for the list itself.

0 votes

**Iterative Method**

- Initialize three pointers prev as NULL, curr as head and next as NULL.
- Iterate trough the linked list. In loop, do following.

// Before changing next of current,

// store next node

next = curr->next// Now change next of current

// This is where actual reversing happens

curr->next = prev// Move prev and curr one step forward

prev = curr

curr = next

// Iterative C program to reverse a linked list #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to reverse the linked list */ static void reverse(struct Node** head_ref) { struct Node* prev = NULL; struct Node* current = *head_ref; struct Node* next = NULL; while (current != NULL) { // Store next next = current->next; // Reverse current node's pointer current->next = prev; // Move pointers one position ahead. prev = current; current = next; } *head_ref = prev; } /* Function to push a node */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Function to print linked list */ void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 85); printf("Given linked list\n"); printList(head); reverse(&head); printf("\nReversed Linked list \n"); printList(head); getchar(); }

**Time Complexity:** O(n)

**Space Complexity:** O(1)

52,345 questions

60,484 answers

201,812 comments

95,288 users