LC-21：合并两个有序链表
LC-21：合并两个有序链表：
我的算法思路实现一：
public class AtomicDemone {
public static void main(String[] args) {
ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);
node1.next = node2;
node2.next = node3;
ListNode node5 = new ListNode(1);
ListNode node6 = new ListNode(3);
ListNode node7 = new ListNode(4);
node5.next = node6;
node6.next = node7;
ListNode listNode = mergeTwoLists(node1, node5);
while (listNode != null) {
System.out.println(listNode.val);
listNode = listNode.next;
}
}
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ArrayList<Integer> list = new ArrayList<>();
while (list1 != null) {
list.add(list1.val);
list1 = list1.next;
}
while (list2 != null) {
list.add(list2.val);
list2 = list2.next;
}
Collections.sort(list);
ListNode result = new ListNode(-1);
ListNode current = result;
for (int i = 0; i < list.size(); i++) {
current.next = new ListNode(list.get(i));
current = current.next;
}
return result.next;
}
}
主要思路：使用ArrayList对两个链表进行遍历。记录里面的所有的元素，然后使用JDK的集合工具类Collections.sort(list)进行排序，然后对list集合中的所有的元素进行遍历，实现对每一个结点创建构建链表，然后然后链表。
我的算法思路实现二：
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode result = new ListNode(-1);
ListNode current = result;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) { // 对于list1中的值小于等于list2 ，那就是存list1中的值
current.next = new ListNode(list1.val); // 存在新的链表中
current = current.next;
list1 = list1.next;
} else { // 对于list1中的值大于list2 ，那就是存list2中的值
current.next = new ListNode(list2.val); // 存在新的链表中
current = current.next;
list2 = list2.next;
}
}
// 对list1进行判空
if (list1 != null) {
current.next = list1;
}
// 对list2进行判空
if (list2 != null) {
current.next = list2;
}
return result.next;
}
if (list1.val <= list2.val) { // 对于list1中的值小于等于list2 ，那就是存list1中的值
current.next = new ListNode(list1.val); // 存在新的链表中
current = current.next;
list1 = list1.next;
} else { // 对于list1中的值大于list2 ，那就是存list2中的值
current.next = new ListNode(list2.val); // 存在新的链表中
current = current.next;
list2 = list2.next;
}
会发现，在if-else中对于链表的后移都是不同的，谁的值存放了就往后移动，这样的话，能够确保就算不是同一个上下位置的话，我也能够保持数据的比较。
最后，我要对list1和list2要进行判断是否有多余的元素，因为这个链表是一个有序的，所以，若是有多余的，就直接连接，反正list1或list2的指针是一直往后移动的。
// 对list1进行判空
if (list1 != null) {
current.next = list1;
}
// 对list2进行判空
if (list2 != null) {
current.next = list2;
}
查看5道真题和解析