Merge two sorted linked lists
Given two sorted linked lists, merge them so that the resulting linked list is also sorted. Consider two sorted linked lists and the merged list below them as an example. %0 node_1 head1 node_2 4 node_1->node_2 node_3 8 node_2->node_3 node_1592253395443 15 node_3->node_1592253395443 node_1592253478417 19 node_1592253395443->node_1592253478417 node_1592253525413 NULL node_1592253478417->node_1592253525413 %0 node_1 head2 node_2 7 node_1->node_2 node_3 9 node_2->node_3 node_1592253395443 10 node_3->node_1592253395443 node_1592253478417 16 node_1592253395443->node_1592253478417 node_1592253525413 NULL node_1592253478417->node_1592253525413 %0 node_1 head1 node_2 4 node_1->node_2 node_3 7 node_2->node_3 node_1592253395443 8 node_3->node_1592253395443 node_1592253478417 9 node_1592253395443->node_1592253478417 node_1592253525413 10 node_1592253478417->node_1592253525413 node_1592253587407 15 node_1592253525413->node_1592253587407 node_1592253604112 16 node_1592253587407->node_1592253604112 node_1592253591340 19 node_1592253604112->node_1592253591340 node_1592253558766 NULL node_1592253591340->node_1592253558766
Runtime Complexity: Linear, O(m+n)O(m + n)O(m+n) where m and n are lengths of both linked lists
Memory Complexity: Constant, O(1)O(1)O(1)
Maintain a head and a tail pointer on the merged linked list. Then choose the head of the merged linked list by comparing the first node of both linked lists. For all subsequent nodes in both lists, you choose the smaller current node and link it to the tail of the merged list, and moving the current pointer of that list one step forward.
Continue this while there are some remaining elements in both the lists. If there are still some elements in only one of the lists, you link this remaining list to the tail of the merged list. Initially, the merged linked list is NULL.
Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list. In this example, it is 4 from head1. Since it’s the first and only node in the merged list, it will also be the tail. Then move head1 one step forward.
What is Python? What are the benefits of using Python
Python is a high-level, interpreted, general-purpose programming language. Being a general-purpose language, it can be used to build almost any type of application with the right tools/libraries. Additionally, python supports objects, modules, threads, exception-handling, and automatic memory management which help in modelling real-world problems and building applications to solve these problems.
Benefits of using Python:
4 What is init method in python?
The init method works similarly to the constructors in Java. The method is run as soon as an object is instantiated. It is useful for initializing any attributes or default behaviour of the object at the time of instantiation. For example:
What is a dynamically typed language?
Before we understand a dynamically typed language, we should learn about what typing is. Typing refers to type-checking in programming languages. In a strongly-typed language, such as Python, “1” + 2 will result in a type error since these languages dont allow for “type-coercion” (implicit conversion of data types). On the other hand, a weakly-typed language, such as Javascript, will simply output “12” as result.
Type-checking can be done at two stages –
Python is an interpreted language, executes each statement line by line and thus type-checking is done on the fly, during execution. Hence, Python is a Dynamically Typed Language.