Task description: You are given the heads of two sorted linked lists and . list1 list2 Merge the two lists into one list. The list should be made by splicing together the nodes of the first two lists. sorted Return . the head of the merged linked list Example 1: Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4] Example 2: Input: list1 = [], list2 = []
Output: [] Example 3: Input: list1 = [], list2 = [0]
Output: [0] Constraints: The number of nodes in both lists is in the range . [0, 50] -100 <= Node.val <= 100 Both and are sorted in order. list1 list2 non-decreasing Reasoning: is another widely used data structure. It could be singly linked or doubly linked. LinkedList For this particular task we can assume that we work with singly linked version. As you can see every linked list consists of small pieces called Links or Node. https://gist.github.com/RakhmedovRS/341071fbc066bcf4a3b2c228e51fc7ff As you can see from the pictures and code above every LinkedNode stores a link to the next LinkedNode. The first LinkedNode is usually called the head whereas the last one is called the tail. With a singly linked version we can only traverse from the head to the tail of the list and there’s no way to return to the previous node once we stepped forward. The doubly linked version allows us to traverse in both directions because every ListNode stores pointers to the next and previous ListNodes. Solution: This time I provide the full code for the solution and we’ll discuss it https://gist.github.com/RakhmedovRS/9d7bff26fae314a46d13420028842992 The first thing we do is  to create a dummy node for storing links to the future head of the merged linked list, as I said previous every LinkedList has a head. We also need a current node for storing the link of the current node, so we can use it to attach next node to it We iterate through both lists till pointers to next nodes are not null. On every such step, we’re looking for a node with minimal value stored in it. We move the pointer to the next for LinkedList which has a current node with minimal value. Eventually one of the pointers of both is null. The last thing we need to do is to attach the rest of LinkedList which still has some values to our current pointer and return a head of the newly created LinkedList. The solution above has linear time complexity and doesn’t use additional memory(In terms of big O notation additional pointers can be omitted) See you in the next article✌️✌️✌️✌️✌️✌️✌️

Java Algorithms: Coding a Binary Tree Right Side View (LeetCode)

How to Implement Trie (Prefix Tree) - Blind 75 LeetCode Questions

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Too Long; Didn't Read

Make resilience your competitive advantage

How To Merge Two Sorted Lists

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Validate Binary Search Tree Blind 75 LeetCode Question

A Hacker's Guide to Competitive Programming

30 Days DSA Interview Preparation Plan

7 Essential Tips for Competitive Programming and DSA

Binary Lifting and Its Applications

Validate Binary Search Tree Blind 75 LeetCode Question

A Hacker's Guide to Competitive Programming

30 Days DSA Interview Preparation Plan

7 Essential Tips for Competitive Programming and DSA

Binary Lifting and Its Applications

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps