Traversal in Linked List

Intuition

Start iterating from the head of the linked list and keep moving to the subsequent node until we reach the end node, which points to NULL.

Approach

Initialize a pointer variable let's say temp to store the copy of the original linked list's head because we need to preserve the original list.
Declare a vector data structure let's say ans to store the result.
Keep traversing the linked list and store the value of the present node in the ans vector, until the next node points to null. Return the ans vector.

Dry Run

#include <bits/stdc++.h>
using namespace std;


struct ListNode {
    int val; 
    ListNode* next;
    ListNode(int data1) : val(data1), next(nullptr) {} 
    ListNode(int data1, ListNode* next1) : val(data1), next(next1) {} 
};


class Solution {
public:
    //Function for Linked List Traversal
    vector<int> LLTraversal(ListNode* head) {
        //Storing a copy of the linked list
        ListNode* temp = head;
        //To store the values 
        //Sequentially
        vector<int> ans;

        //Keep traversing
        //Until the nullptr 
        //Is not encountered
        while (temp != nullptr) {
            //Storing of the values
            ans.push_back(temp->val);
            //Storing the address of the next node
            temp = temp->next;
        }
        //Return answer 
        return ans;
    }
};

int main() {
    //Manual creation of nodes
    ListNode* y1 = new ListNode(2);
    ListNode* y2 = new ListNode(5);
    ListNode* y3 = new ListNode(8);
    ListNode* y4 = new ListNode(7);

    // Linking the nodes
    y1->next = y2;
    y2->next = y3;
    y3->next = y4;

    //Instance of
    //Solution class
    Solution sol;

    //Calling LLTraversal method 
    //To get the values
    vector<int> result = sol.LLTraversal(y1);

    //Printing the result
    cout << "Linked List Values:" << endl;
    for (int val : result) {
        cout << val << " ";
    }
    cout << endl;

    //Clean up 
    //Allocated memory
    delete y1;
    delete y2;
    delete y3;
    delete y4;

    return 0;
}
import java.io.*;

class ListNode {
    int val; 
    ListNode next; 
    ListNode(int data1) {
        val = data1;
        next = null;
    }

    ListNode(int data1, ListNode next1) {
        val = data1;
        next = next1;
    }
}


class Solution {
     //Function for Linked List Traversal
    public List<Integer> LLTraversal(ListNode head) {
        //Storing a copy of the linked list
        ListNode temp = head;
        //To store the values sequentially
        List<Integer> ans = new ArrayList<>();
        
        //Keep traversing
        //Until null is encountered
        while (temp != null) {
            //Storing the values
            ans.add(temp.val);
            //Storing the address of the next node
            temp = temp.next;
        }
        //Return answer
        return ans;
    }
}

public class Main {
    public static void main(String[] args) {
        //Manual creation of nodes
        ListNode y1 = new ListNode(2);
        ListNode y2 = new ListNode(5);
        ListNode y3 = new ListNode(8);
        ListNode y4 = new ListNode(7);

        // Linking the nodes
        y1.next = y2;
        y2.next = y3;
        y3.next = y4;

        // Creating an instance of 
        //Solution class
        Solution solution = new Solution();

        // Calling LLTraversal method 
        //To get the values
        List<Integer> result = solution.LLTraversal(y1);

        // Printing the result
        System.out.println("Linked List Values:");
        for (int val : result) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function for Linked List Traversal
    def LLTraversal(self, head: ListNode) -> list:
        # Storing a copy 
        #Of the linked list
        temp = head
        #To store 
        #Values sequentially
        ans = []

        #Keep traversing
        #Until the None 
        #Is not encountered
        while temp is not None:
            #Storing of the values
            ans.append(temp.val)
            #Storing the address 
            #Of the next node
            temp = temp.next

        #Returning the answer 
        return ans

if __name__ == "__main__":
    #Manual creation of nodes
    y1 = ListNode(2)
    y2 = ListNode(5)
    y3 = ListNode(8)
    y4 = ListNode(7)

    #Linking the nodes
    y1.next = y2
    y2.next = y3
    y3.next = y4

    #Solution class
    sol = Solution()

    #Calling LLTraversal method
    result = sol.LLTraversal(y1)

    #Printing the result
    print("Linked List Values:")
    for val in result:
        print(val, end=" ")
    print()
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    //Function for 
    //Linked List Traversal
    LLTraversal(head) {
        //Storing a copy 
        //Of the linked list
        let temp = head;
        //To store the 
        //Values sequentially
        let ans = [];

        //Keep traversing 
        //Until the null is 
        //Not encountered
        while (temp !== null) {
            // Storing of the values
            ans.push(temp.val);
            //Storing the address 
            //Of the next node
            temp = temp.next;
        }

        //Return answer 
        return ans;
    }
}

//Manual creation of nodes
let y1 = new ListNode(2);
let y2 = new ListNode(5);
let y3 = new ListNode(8);
let y4 = new ListNode(7);

//Linking the nodes
y1.next = y2;
y2.next = y3;
y3.next = y4;

//Solution instance
let sol = new Solution();

// Calling LLTraversal method to get the values
let result = sol.LLTraversal(y1);

// Printing the result
console.log("Linked List Values:");
for (let val of result) {
    console.log(val + " ");
}

Complexity Analysis

Time Complexity: O(N) since we are visiting each node once. Here N represents the length of the linked list or the number of nodes present in the linked list.

Space Complexity: O(N) since we are storing the result in a vector.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code