合并两个排序的链表并将其作为新列表返回。新列表也应该排序。
例子:
Input:
1->2->4
1->3->4
Output: 1->1->2->3->4->4
初始化一个表示合并列表 (result
) 的新 LinkedList。现在,遍历两个列表(l1
和 l2
),并为每次迭代
result
)这是完整的实现:
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
class MergeSortedLinkedList {
private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
ListNode result = null;
ListNode head = null;
while(l1 != null || l2 != null) {
int minVal;
if (l1 == null) {
minVal = l2.val;
l2 = l2.next;
} else if (l2 == null) {
minVal = l1.val;
l1 = l1.next;
} else if(l1.val <= l2.val) {
minVal = l1.val;
l1 = l1.next;
} else {
minVal = l2.val;
l2 = l2.next;
}
if(result == null) {
result = head = new ListNode(minVal);
} else {
result.next = new ListNode(minVal);
result = result.next;
}
}
return head;
}
public static void main(String[] args) {
ListNode l1 = new ListNode(1);
l1.next = new ListNode(2);
l1.next.next = new ListNode(4);
ListNode l2 = new ListNode(1);
l2.next = new ListNode(3);
l2.next.next = new ListNode(4);
ListNode mergedList = mergeSortedLinkedLists(l1, l2);
while(mergedList != null) {
System.out.print(mergedList.val + " ");
mergedList = mergedList.next;
}
System.out.println();
}
}
# Output
$ javac MergeSortedLinkedList.java
$ java MergeSortedLinkedList
1 1 2 3 4 4
请注意,我们正在为生成的链接列表创建新节点,而不是直接使用提供的链接列表的节点。此解决方案将使用额外空间,但建议在现实世界中使用,因为我们不会修改参数中提供的 LinkedLists。
如果您不想创建新节点,则可以直接使用提供的 LinkedList 节点:
private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
ListNode result = null;
ListNode head = null;
while(l1 != null || l2 != null) {
ListNode minNode;
if (l1 == null) {
minNode = l2;
l2 = l2.next;
} else if (l2 == null) {
minNode = l1;
l1 = l1.next;
} else if(l1.val <= l2.val) {
minNode = l1;
l1 = l1.next;
} else {
minNode = l2;
l2 = l2.next;
}
if(result == null) {
result = head = minNode;
} else {
result.next = minNode;
result = result.next;
}
}
return head;
}
您还可以使用递归来合并链表。以下函数显示了递归方法:
private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
if(l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
}
ListNode result = null;
if(l1.val <= l2.val) {
result = new ListNode(l1.val);
result.next = mergeSortedLinkedLists(l1.next, l2);
} else {
result = new ListNode(l2.val);
result.next = mergeSortedLinkedLists(l1, l2.next);
}
return result;
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://www.callicoder.com/merge-two-sorted-linked-lists/
内容来源于网络,如有侵权,请联系作者删除!