本题目解答思路:(1)先将两个无序的链接排序(2)将排序后的列表合并
// 链表类
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
// 连接两个单项链表,返回排序后的结果
public static ListNode unionTwoLinkTable(ListNode list1, ListNode list2) {
if (list1 != null) {
// 将list1变为有序的
for (ListNode ln1 = list1; ln1.next != null; ln1 = ln1.next) {
if (ln1.val > ln1.next.val) {
int temp = ln1.val;
ln1.val = ln1.next.val;
ln1.next.val = temp;
}
}
}
if (list2 != null) {
// 将list2变为有序的
for (ListNode ln2 = list2; ln2.next != null; ln2 = ln2.next) {
if (ln2.val > ln2.next.val) {
int temp = ln2.val;
ln2.val = ln2.next.val;
ln2.next.val = temp;
}
}
}
ListNode head, tmp;
if (list1.val <= list2.val) {
tmp = list1;
list1 = list1.next;
} else {
tmp = list2;
list2 = list2.next;
}
head = tmp;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
tmp.next = list1;
tmp = list1;
list1 = list1.next;
} else {
tmp.next = list2;
tmp = list2;
list2 = list2.next;
}
}
if (list1 != null)
tmp.next = list1;
if (list2 != null)
tmp.next = list2;
return head;
}
//输出
public static ArrayList printListFromTailToHead(ListNode listNode) {
ArrayList li = new ArrayList();
if (listNode == null) {
return li;
}
li.add(listNode.val);
for (ListNode ln = listNode.next; ln != null; ln = ln.next) {
li.add(ln.val);
}
for (int i = 0; i < li.size(); i++)
System.out.print(li.get(i) + " ");
System.out.println();
return li;
}