Convert Array to DLL

Linked-List Fundamentals (Doubly LL) Easy

Given an array nums, convert it into a doubly linked list and return the head of the list.

Examples:

Input: nums = [1, 2, 3, 4]

Output: head -> 1 <-> 2 <-> 3 <-> 4

Input: nums = [7, 7]

Output: head -> 7 <-> 7

Input: nums = [3]

Constraints

n == nums.length
0 <= n <= 100
0 <= nums[i] <= 100

Hints

Create a Node structure containing val, next, and prev pointers. Initialize the head with the first element of nums[].
Iterate through nums[], creating new nodes, linking them bidirectionally (prev and next). Return the head of the doubly linked list.

Company Tags

Ernst & Young Zynga Epic Systems Qualcomm Medtronic HCL Technologies Flipkart Deloitte Oracle Intel Snowflake Teladoc Health Splunk Cloudflare GE Healthcare Broadcom Bungie Bloomberg Stripe Twilio Visa Morgan Stanley ARM eBay MongoDB TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Begin the conversion of an array to a doubly linked list by creating the head node of the list. Then, iterate over each array element, constructing a new node for each element encountered. As each new node is created, link its next pointer to the subsequent node in the list, and link its back pointer to the preceding node. Upon completion, the head of the doubly linked list can be returned as the final result.

Approach:

Begin by creating the head of the doubly linked list (DLL) using the first element of the array. Set both the previous and next pointers of this node to NULL, as it is the first node in the list.
Iterate over the array starting from the second element, i.e., from index 1 to the last element of the array.
For each element in the array, create a new node with the current value from the array. Set the backward link of this new node to point to the node created in the previous step, establishing a connection to the previous node.
Update the forward link of the node from the previous iteration to connect it to the newly created node, establishing a forward connection.
Shift the reference of the previous node to the newly created node, which will serve as the previous node for the next iteration.
Repeat this process for each element in the array. Once the iteration is complete, the head node represents the start of the doubly linked list and can be returned as the final result.

Dry Run:

Solution:

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

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    // Function to convert an array to a doubly linked list
    ListNode* arrayToLinkedList(vector<int> &nums) {
        // If array is empty, return nullptr
        if (nums.empty()) return nullptr; 

        // Create head node with first element of the array
        ListNode* head = new ListNode(nums[0]); 
        // Initialize 'prev' to the head node
        ListNode* prev = head;             

        for (int i=1; i < nums.size(); i++) {
            // Create a new node 
            ListNode* temp = new ListNode(nums[i], nullptr, prev);
            // Update 'next' pointer
            prev->next = temp;    
            // Move 'prev' to newly created node
            prev = temp;         
        }
        
        // Return head
        return head;  
    }
};

// Helper Function to print the linked list
void printLL(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    
    // Create an instance of Solution class 
    Solution sol;
    
    // Function call to convert an array to a doubly linked list
    ListNode* head = sol.arrayToLinkedList(nums);

    // Print the doubly linked list
    cout << "The doubly linked list is: ";
    printLL(head);

    return 0;
}
// Definition of doubly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    ListNode() {
        val = 0;
        next = null;
        prev = null;
    }

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

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

// Solution class
class Solution {
    // Function to convert an array to a doubly linked list
    public ListNode arrayToLinkedList(int[] nums) {
        // If array is empty, return null
        if (nums.length == 0) return null;

        // Create head node with first element of the array
        ListNode head = new ListNode(nums[0]);
        // Initialize 'prev' to the head node
        ListNode prev = head;

        for (int i = 1; i < nums.length; i++) {
            // Create a new node
            ListNode temp = new ListNode(nums[i], null, prev);
            // Update 'next' pointer
            prev.next = temp;
            // Move 'prev' to newly created node
            prev = temp;
        }

        // Return head
        return head;
    }
}

// Main Class
class Main {
    // Helper function to print the linked list
    private static void printLL(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    
    // main method
    public static void main(String[] args) {
        // Declare nums as a 1D array
        int[] nums = {1, 2, 3, 4, 5};

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Function call to convert an array to a doubly linked list
        ListNode head = sol.arrayToLinkedList(nums);

        // Print the doubly linked list
        System.out.println("The doubly linked list is: ");
        printLL(head);
    }
}
# Definition of doubly linked list
class ListNode:
    def __init__(self, data1=0, next1=None, prev1=None):
        self.val = data1
        self.next = next1
        self.prev = prev1

# Solution class
class Solution:
    # Function to convert an array to a doubly linked list
    def arrayToLinkedList(self, nums):
        # If array is empty, return None
        if not nums:
            return None

        # Create head node with first element of the array
        head = ListNode(nums[0])
        # Initialize 'prev' to the head node
        prev = head

        for i in range(1, len(nums)):
            # Create a new node
            temp = ListNode(nums[i], None, prev)
            # Update 'next' pointer
            prev.next = temp
            # Move 'prev' to newly created node
            prev = temp

        # Return head
        return head

# Helper function to print the linked list
def printLL(head):
    while head is not None:
        print(head.val, end=" ")
        head = head.next
    print()

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]

    # Create an instance of Solution class
    sol = Solution()

    # Function call to convert an array to a doubly linked list
    head = sol.arrayToLinkedList(nums)

    # Print the doubly linked list
    print("The doubly linked list is: ")
    printLL(head)
// Definition of doubly linked list
class ListNode {
    constructor(data1 = 0, next1 = null, prev1 = null) {
        this.val = data1;
        this.next = next1;
        this.prev = prev1;
    }
}

// Solution class
class Solution {
    // Function to convert an array to a doubly linked list
    arrayToLinkedList(nums) {
        // If array is empty, return null
        if (nums.length === 0) return null;

        // Create head node with first element of the array
        let head = new ListNode(nums[0]);
        // Initialize 'prev' to the head node
        let prev = head;

        for (let i = 1; i < nums.length; i++) {
            // Create a new node
            let temp = new ListNode(nums[i], null, prev);
            // Update 'next' pointer
            prev.next = temp;
            // Move 'prev' to newly created node
            prev = temp;
        }

        // Return head
        return head;
    }
}

// Helper function to print the linked list
function printLL(head) {
    while (head !== null) {
        process.stdout.write(head.val + " ");
        head = head.next;
    }
    console.log();
}

const main = () => {
    let nums = [1, 2, 3, 4, 5];

    // Create an instance of Solution class
    let sol = new Solution();

    // Function call to convert an array to a doubly linked list
    let head = sol.arrayToLinkedList(nums);

    // Print the doubly linked list
    console.log("The doubly linked list is: ");
    printLL(head);
}

main();

Complexity Analysis:

Time Complexity: O(N) where N is the length of the array. The code iterates over the array once creating a new node for each element. Space Complexity: O(N) The space complexity depends on the memory used to store doubly linked list nodes. Each node, storing data and two pointers ('next' and 'back'), requires constant space. Thus, space complexity is O(N) as it scales linearly with the array's size.

Code

Problem List