🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
In this blog post, we'll delve into a common algorithmic problem in the realm of data structures: merging two sorted linked lists in Java. This problem is a must in programming interviews and is crucial for understanding how to manipulate and merge linked lists.
Problem
Given two sorted linked lists, the goal is to merge them into a single, sorted linked list. The final merged list should also be sorted.
Example:
Input:
1->2->4,
1->3->4
Output:
1->1->2->3->4->4
2. Solution Steps
1. Create a dummy head node to simplify the merging process.
2. Use two pointers, each pointing to the head of the two lists.
3. Compare the node values where the pointers are currently pointing.
4. Append the smaller value to the merged list and move the pointer of that list forward.
5. Continue the process until one of the lists is completely traversed.
6. Append the remaining part of the non-empty list to the merged list.
7. Return the next node of the dummy head as the head of the merged list.
3. Code Program
public class ListNode {
int val; // Value of the node
ListNode next; // Reference to the next node
// Constructor to initialize the node with a value
ListNode(int x) { val = x; }
// Method to print the linked list starting from this node
void printList() {
ListNode temp = this;
while(temp != null) {
System.out.print(temp.val + " "); // Print the value of the current node
temp = temp.next; // Move to the next node
}
System.out.println();
}
}
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0); // Dummy head to simplify list manipulation
ListNode current = dummyHead; // Pointer to build the new list
// Iterate as long as both lists have nodes
while (l1 != null && l2 != null) {
if (l1.val < l2.val) { // Compare values of the two nodes
current.next = l1; // Link the smaller node
l1 = l1.next; // Move forward in list l1
} else {
current.next = l2; // Link the smaller node
l2 = l2.next; // Move forward in list l2
}
current = current.next; // Move to the next node in the merged list
}
// Link the remaining part of the list that is not null
current.next = (l1 != null) ? l1 : l2;
return dummyHead.next; // Return the merged list, excluding the dummy head
}
}
// Example usage and testing
public class Main {
public static void main(String[] args) {
ListNode l1 = new ListNode(1); // First node of first list
l1.next = new ListNode(2); // Second node of first list
l1.next.next = new ListNode(4); // Third node of first list
ListNode l2 = new ListNode(1); // First node of second list
l2.next = new ListNode(3); // Second node of second list
l2.next.next = new ListNode(4); // Third node of second list
Solution solution = new Solution();
ListNode mergedList = solution.mergeTwoLists(l1, l2);
mergedList.printList(); // Print the merged list
}
}
Output:
1 1 2 3 4 4
Explanation:
The input lists are 1->2->4 and 1->3->4.
The mergeTwoLists method merges these two lists by comparing the nodes of each list and appending the smaller node to the merged list.
The process continues until all nodes in both lists are merged, resulting in the sorted output 1->1->2->3->4->4.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment