1,合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
2,示例
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
3,题解思路
哨兵节点的使用
4,题解程序
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class MergeTwoListsTest {
public static void main(String[] args) {
ListNode l11 = new ListNode(1);
ListNode l12 = new ListNode(2);
ListNode l13 = new ListNode(4);
l11.next = l12;
l12.next = l13;
ListNode l21 = new ListNode(1);
ListNode l22 = new ListNode(3);
ListNode l23 = new ListNode(4);
l21.next = l22;
l22.next = l23;
ListNode listNode = mergeTwoLists2(l11, l21);
System.out.println("listNode = " + listNode);
}
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummyNode = new ListNode(-1);
ListNode temp = dummyNode;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
temp.next = l1 == null ? l2 : l1;
return dummyNode.next;
}
public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
List<Integer> list = new ArrayList<>();
while (l1 != null) {
list.add(l1.val);
l1 = l1.next;
}
while (l2 != null) {
list.add(l2.val);
l2 = l2.next;
}
ListNode dummyNode = new ListNode(-1);
ListNode tempNode = dummyNode;
Collections.sort(list);
for (Integer num : list
) {
tempNode.next = new ListNode(num);
tempNode = tempNode.next;
}
return dummyNode.next;
}
}
5,题解程序图片版
6,总结
这道题理解起来还是比较容易的对吧,两两比较,然后将较小的数据挂载dummyNode节点后面,这就是使用哨兵节点的好处,一般链表都或多或少的增加一个哨兵节点来处理数据。