Description:
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Examples:
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]Solution in Python:
To merge two sorted linked lists into one sorted linked list in Python, you can follow these steps:
- Create a Dummy Node: This dummy node will help in easily managing the head of the merged linked list.
- Initialize Pointers: Use two pointers to traverse through the given linked lists and another pointer to build the merged linked list.
- Compare Nodes: At each step, compare the current nodes of both lists and attach the smaller node to the merged list.
- Advance Pointers: Move the pointer of the list from which the node was taken forward.
- Attach Remaining Nodes: After one list is exhausted, attach the remaining nodes of the other list to the merged list.
- Return the Merged List: The head of the merged list is the next node of the dummy node.
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
# Create a dummy node to simplify the merging process
dummy = ListNode()
current = dummy
# Traverse through both lists
while list1 and list2:
# Compare the current nodes of both lists
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
# Move the current pointer of the merged list
current = current.next
# Attach the remaining nodes of list1, if any
if list1:
current.next = list1
# Attach the remaining nodes of list2, if any
if list2:
current.next = list2
# The head of the merged list is the next node of the dummy node
return dummy.next
# Example usage:
# list1 = [1,2,4], list2 = [1,3,4]
# Construct the linked lists from the arrays
def build_list(arr):
dummy = ListNode()
current = dummy
for num in arr:
current.next = ListNode(num)
current = current.next
return dummy.next
def print_list(head):
current = head
while current:
print(current.val, end=" -> ")
current = current.next
print("None")
# Create the linked lists
list1 = build_list([1, 2, 4])
list2 = build_list([1, 3, 4])
# Merge the lists
solution = Solution()
merged_list = solution.mergeTwoLists(list1, list2)
# Print the merged list
print_list(merged_list) # Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> NoneExplanation:
- Definition of
ListNode:- The
ListNodeclass represents a node in the linked list.
- The
mergeTwoListsMethod:- The method takes two sorted linked lists (
list1andlist2) and returns a single sorted linked list. - A dummy node is created to simplify the list merging process.
- The
currentpointer is used to build the new merged list. - A while loop iterates through both lists, comparing nodes and attaching the smaller node to the merged list.
- If one list is exhausted before the other, the remaining nodes of the non-exhausted list are attached to the merged list.
- Finally, the method returns the merged list starting from
dummy.next.
- The method takes two sorted linked lists (
- Helper Functions:
build_listconverts an array into a linked list.print_listprints the linked list for verification.
This solution ensures that the merged list is sorted and efficiently handles the merging process in linear time.
Solution in Javascript:
JavaScript
// Definition for singly-linked list.
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
var mergeTwoLists = function(list1, list2) {
// Create a dummy node to simplify the merging process
let dummy = new ListNode();
let current = dummy;
// Traverse through both lists
while (list1 !== null && list2 !== null) {
// Compare the current nodes of both lists
if (list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
// Move the current pointer of the merged list
current = current.next;
}
// Attach the remaining nodes of list1, if any
if (list1 !== null) {
current.next = list1;
}
// Attach the remaining nodes of list2, if any
if (list2 !== null) {
current.next = list2;
}
// The head of the merged list is the next node of the dummy node
return dummy.next;
};Solution in Java:
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// Create a dummy node to serve as the start of the merged list
ListNode dummy = new ListNode(0);
// Initialize current to point to the dummy node
ListNode current = dummy;
// Traverse both lists until one of them is exhausted
while (list1 != null && list2 != null) {
// Compare the values of the current nodes of both lists
if (list1.val <= list2.val) {
// If list1's value is smaller or equal, append it to the merged list
current.next = list1;
// Move the pointer of list1 forward
list1 = list1.next;
} else {
// If list2's value is smaller, append it to the merged list
current.next = list2;
// Move the pointer of list2 forward
list2 = list2.next;
}
// Move the current pointer forward
current = current.next;
}
// At this point, at least one of the lists is exhausted
// Append the remaining nodes of the non-exhausted list
if (list1 != null) {
current.next = list1;
} else {
current.next = list2;
}
// Return the head of the merged list, which is next of dummy
return dummy.next;
}
}Solution in C#:
C#
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
// Create a dummy node to simplify the merging process
ListNode dummy = new ListNode();
ListNode current = dummy;
// Traverse through both lists
while (list1 != null && list2 != null) {
// Compare the current nodes of both lists
if (list1.val < list2.val) {
current.next = list1;
list1 = list1.next;
} else {
current.next = list2;
list2 = list2.next;
}
// Move the current pointer of the merged list
current = current.next;
}
// Attach the remaining nodes of list1, if any
if (list1 != null) {
current.next = list1;
}
// Attach the remaining nodes of list2, if any
if (list2 != null) {
current.next = list2;
}
// The head of the merged list is the next node of the dummy node
return dummy.next;
}
}