Traversal in Linked List

Linked-List Fundamentals (Single LL) Easy Go Ad-Free - ₹20/mo

Given the head of a singly Linked List. Traverse the entire Linked List and return its elements in an array in the order of their appearance.

Examples:

Input: head -> 5 -> 4 -> 3 -> 1 -> 0

Output: [5, 4, 3, 1, 0]

Explanation: The nodes in the Linked List are 5 -> 4 -> 3 -> 1 -> 0, with the head pointing to node with value 5.

Input: head -> 1

Output: [1]

Explanation: Only one node present in the list.

Input: head -> 0 -> 2 -> 5

Constraints

0 <= number of nodes in the Linked List <= 10⁵
0 <= ListNode.val <= 10⁴

Hints

Start at the head node. Use a loop to traverse through each node of the linked list.
Initialize an empty array to store the values. Use a pointer to traverse the list. When the pointer becomes null or None, the traversal is complete.

Company Tags

Zoho Freshworks McKinsey & Company Splunk Robinhood Micron Technology Bain & Company MongoDB Philips Healthcare HCL Technologies American Express Uber OYO Rooms PwC AMD Cerner Broadcom ARM Walmart Ubisoft Etsy Teladoc Health Nutanix Alibaba Goldman Sachs TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/8pSAcR8d7Tu/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

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.

Frequently Occurring Doubts

Q: How do you handle very large linked lists?

A: The iterative approach is preferred for large lists because it avoids the stack overflow risk associated with recursion.

Q: How do you confirm the traversal order?

A: The traversal order is guaranteed to be the same as the linked list order because each node is processed sequentially.

Interview Followup Questions

Q: What if you need to reverse the traversal order?

A: Use a stack to store the values during traversal and pop elements from the stack to get them in reverse order. Alternatively, reverse the array after traversal.

Q: Can this algorithm be parallelized?

A: Traversing a singly linked list cannot be parallelized because each node depends on the next pointer of the previous node. However, parallelization is possible for tasks performed on the data after traversal.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories