-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmergeTwoSorted.java
More file actions
68 lines (59 loc) · 1.92 KB
/
mergeTwoSorted.java
File metadata and controls
68 lines (59 loc) · 1.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.*;
// import ListNode;
//* Definition for singly-linked list.
// public static 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 mergeTwoSorted {
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(0); // Dummy node to start merged list
ListNode current = dummy;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
current.next = list1; // Link the smaller node
list1 = list1.next; // Move the list1 forward
} else {
current.next = list2; // Link the smaller node
list2 = list2.next; // Move list2 forward
}
current = current.next; // Move current forward
}
// Link remaining nodes from list1 or list2
if (list1 != null) {
current.next = list1;
} else {
current.next = list2;
}
return dummy.next; // Head of the merged list
}
public static void printList(ListNode head) {
ListNode temp = head;
while (temp != null) {
System.out.print(temp.val + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args) {
// Create first list
ListNode list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
ListNode list2 = new ListNode(1, new ListNode(3, new ListNode(4)));
System.out.println("Merged List: ");
ListNode mergedList = mergeTwoLists(list1, list2);
printList(mergedList);
}
}
/*
* Imports the ListNode from the reversed LL
* to compile,
* javac ListNode.java mergeTwoSorted.java
*
* to run:
* java mergeTwoSorted.java
*
*
*/