Problem Statement

You are given the head of the linked list, you need to traverse and print the value of every node of the linked list.

Examples

Example 1:

Input: list = 1->2->3->4->5->6->7
Output:
1
2
3
4
5
6
7

Explanation: Value of every node of the given linked list
is printed.

Different Approaches

1️⃣ Iteration

Code:

 #include <iostream> // Include the input/output library for console operations

using namespace std; // Use the standard namespace for convenience

// Define a structure for a Node in the linked list
struct Node {
    int val;        // Value stored in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize the node with a value and set 'next' to nullptr
    Node(int val) {
        this->val = val; // Assign the input value to the node
        next = nullptr;  // Initialize 'next' as null (end of the list by default)
    }
};

// Function to traverse and print the linked list using iteration
void traverseUsingIteration(Node* head) {
    Node* temp = head; // Create a temporary pointer to traverse the list
    
    // Loop through the list until the end is reached (temp becomes nullptr)
    while (temp != nullptr) {
        cout << temp->val << endl; // Print the value of the current node
        temp = temp->next;         // Move to the next node
    }
}

int main() {
    // Create a linked list manually by connecting nodes
    Node* head = new Node(1);            // First node with value 1
    head->next = new Node(2);            // Second node with value 2
    head->next->next = new Node(3);      // Third node with value 3
    head->next->next->next = new Node(4);// Fourth node with value 4
    head->next->next->next->next = new Node(5); // Fifth node with value 5
    
    // Call the traversal function to print the list
    traverseUsingIteration(head);

    // Note: The memory allocated using 'new' is not freed in this code,
    // which could lead to memory leaks in larger programs. It's good practice
    // to free the memory when done by deleting all nodes.

    return 0; // Exit the program
}

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes in the list.
• Space Complexity: O(1)
  • As no extra space is needed.

2️⃣ Recursive Approach

Code:

#include <iostream> // Include the input/output stream library

using namespace std; // Use the standard namespace for convenience

// Define a structure for a Node in the linked list
struct Node {
    int val;        // Value stored in the node
    Node* next;     // Pointer to the next node in the list

    // Constructor to initialize the node with a value and set 'next' to nullptr
    Node(int val) {
        this->val = val; // Assign the input value to the node
        next = nullptr;  // Initialize 'next' as null (end of the list by default)
    }
};

// Function to traverse and print the linked list using recursion
void traverseUsingRecursion(Node* node) {
    // Base case: Stop recursion if the current node is null
    if (node == nullptr) {
        return;
    }

    // Print the value of the current node
    cout << node->val << endl;

    // Recursive call: Move to the next node in the list
    traverseUsingRecursion(node->next);
}

int main() {
    // Create a linked list manually by dynamically allocating nodes and linking them
    Node* head = new Node(1);              // First node with value 1
    head->next = new Node(2);              // Second node with value 2
    head->next->next = new Node(3);        // Third node with value 3
    head->next->next->next = new Node(4);  // Fourth node with value 4
    head->next->next->next->next = new Node(5); // Fifth node with value 5

    // Call the recursive function to print the linked list values
    traverseUsingRecursion(head);

    // Note: Memory allocated with 'new' is not freed here, which could lead to memory leaks.
    // In larger programs, it's a good practice to free the memory when done.

    return 0; // Exit the program
}

Output:
1
2
3
4
5

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes in the list.
• Space Complexity: O(n)
  • For a linked list with n nodes, the recursion depth will be n.

🐱‍👓 Reverse Traversal

With the recursion approach, we can easily traverse a linked list in reverse order. This is because recursion inherently uses a call stack to store the state of each node while traversing. When the base case is reached (end of the list), the stack begins to "unwind," allowing the program to process the nodes in reverse order.

1️⃣ Recursive Reverse Traversal:

void reverseTraverseUsingRecursion(Node* node) {
    if (node == nullptr) { // Base case: end of the list
        return;
    }
    // Recursive call for the next node
    reverseTraverseUsingRecursion(node->next);

    // Process the current node (after recursion unwinds)
    cout << node->val << endl;
}

Output:
5
4
3
2
1

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes.
• Space Complexity: O(n), due to the recursion call stack.

2️⃣ Reverse Traversal Using Iteration:

It is not inherently possible to traverse a singly linked list in reverse order using a simple iterative approach. This is because a singly linked list only allows access to the next node in the sequence, and there are no backward links to move to the previous node.

Workarounds for Reverse Traversal Iteratively:

Using a Stack:

• Push all node values onto a stack during a forward traversal.
• Pop values off the stack and print them, which result in reverse order.

void reverseTraverseUsingStack(Node* head) {
    stack<int> s; // Stack to store node values
    Node* temp = head;

    // Traverse the list and push all node values onto the stack
    while (temp != nullptr) {
        s.push(temp->val);
        temp = temp->next;
    }

    // Pop and print values in reverse order
    while (!s.empty()) {
        cout << s.top() << endl;
        s.pop();
    }
}

Complexity Analysis:

• Time Complexity: O(n), for both traversal and stack operations.
• Space Complexity: O(n), due to the stack.

Reverse the List Temporarily:

• Reverse the linked list, traverse it, and then restore the original order.
• This approach modifies the structure temporarily but ensures reverse traversal.

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node* next;

    // Constructor to initialize the node with a value and set next to nullptr
    Node(int val) {
        this->val = val;
        next = nullptr;
    }
};

// Function to reverse the linked list
Node* reverseList(Node* head) {
    Node* prev = nullptr;  // Initially, prev is nullptr (end of the list)
    Node* curr = head;     // Start with the head node
    Node* next = nullptr;  // Temporary pointer to store the next node

    // Reverse the list using iteration
    while (curr != nullptr) {
        next = curr->next;  // Store the next node
        curr->next = prev;  // Reverse the current node's pointer
        prev = curr;        // Move prev to the current node
        curr = next;        // Move to the next node
    }

    // After the loop, prev will point to the new head of the reversed list
    return prev;
}

// Function to traverse the linked list and print its values
void traverse(Node* head) {
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // Create a linked list
    Node* head = new Node(1);            // First node with value 1
    head->next = new Node(2);            // Second node with value 2
    head->next->next = new Node(3);      // Third node with value 3
    head->next->next->next = new Node(4);// Fourth node with value 4
    head->next->next->next->next = new Node(5); // Fifth node with value 5

    cout << "Original List: ";
    traverse(head); // Print the original list

    // Reverse the linked list
    head = reverseList(head);

    cout << "Reversed List: ";
    traverse(head); // Print the reversed list

    return 0;
}

Complexity Analysis:

• Time Complexity: O(n) + O(n) ~ O(n)
  • O(n): For reversing the list.
  • O(n): For traversing the reversed list.
  • Overall: O(n)
• Space Complexity: O(1)
  • As we are reversing the same list.