Merge Two Sorted Lists
Write an algorithm that merges two sorted lists.
Approach
The general idea to approach this problem is to have two pointers for the two lists. There will be another pointer to iterate through the lists and pick the smaller node of the two pointers at each node and move the current pointer along.
ListNode Definition
public class ListNode {
int data;
ListNode next;
public ListNode(data, next) {
this.data = data;
this.next = next;
}
}Implementation
public static ListNode merge(ListNode listOne, ListNode listTwo) {
ListNode pseudoHead = new ListNode(0, null);
ListNode cur = pseudoHead;
while (listOne != null && listTwo != null) {
if (listOne.data < listTwo.data) {
cur.next = listOne;
listOne = listOne.next;
}
else {
cur.next = listTwo;
listTwo = listTwo.next;
}
cur = cur.next;
}
cur.next = (listOne != null) ? listOne : listTwo;
return pseudoHead.next;
}