Doubly to Singly Linked List Conversion

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given the head of a doubly linked list. Your task is to convert this list into a singly linked list in-place.

A doubly linked list node has pointers to both the next and the previous node in the sequence. A singly linked list node only has a pointer to the next node.

To perform the conversion, you must iterate through the list and remove the prev pointer from every node by setting it to null. The sequence of nodes and their data, determined by the next pointers, must remain unchanged.

Your function should return the head of the modified list.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first and only line of input contains the node data for the doubly linked list, separated by single spaces. The input is terminated by -1.

Output Format:

The only line of output prints the elements of the modified singly linked list, separated by spaces.

Note:

You are not required to print anything explicitly. The runner code will take the head node returned by your function and traverse it using only the next pointers to print the final list.

Sample Input 1:

1 2 3 4 -1

Sample Output 1:

1 2 3 4

Explanation for Sample 1:

The function traverses the list and sets the prev pointer of each node (1, 2, 3, 4) to null. The next pointers remain intact. The runner then prints the list, which is still 1 -> 2 -> 3 -> 4.

Sample Input 2:

10 -1

Sample Output 2:

Explanation for Sample 2:

The list has only one node. Its prev pointer is already null. The code should handle this case correctly and return the head node.

Expected Time Complexity:

The expected time complexity is O(n log n).

Constraints:

0 <= Number of nodes <= 5000
-10^9 <= Node.data <= 10^9

Time Limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Doubly to Singly Linked List Conversion

Console