需求
思路
- 排序:讲所有的值都取出来,存储到ArrayList中,然后排序,
将排序之后的元素依次使用add方法添加到自定义链表
- 合并排序:先合并,然后调用刚才写的排序算法
- 合并:将表一的头结点作为新链表的头结点,
表一的尾节点指向表二的头结点
代码
自定义链表
public class MyLinkedList<E> {
Node<E> head = null;
public Node<Integer> merge(Node<Integer> head1, Node<Integer> head2) {
if (head1 == null ) {
return head2;
}
if (head2 == null) {
return head1;
}
Node<Integer> tmp = head1;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = head2;
MyLinkedList<Integer> myLinkedList = new MyLinkedList<>();
myLinkedList.head = head1;
return myLinkedList.sorted();
}
public static class Node<E> {
E data;
Node<E> next;
public Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
public void add(E e) {
Node<E> newNode = new Node<>(e, null);
if (head == null) {
head = newNode;
return;
}
Node<E> temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
public Node<E> sorted() {
if (head == null || head.next == null) {
return head;
}
List<E> list = new ArrayList<>();
while (head != null) {
list.add(head.data);
head = head.next;
}
list.sort((o1, o2) -> {
if (o1 instanceof Integer) {
return (Integer) o1 - (Integer) o2;
}
return 0;
});
MyLinkedList<E> myLinkedList = new MyLinkedList<>();
for (E e : list) {
myLinkedList.add(e);
}
return myLinkedList.head;
}
public static void forEachPrint(MyLinkedList.Node<Integer> sorted1) {
while (sorted1 != null) {
System.out.print(sorted1.data+" ");
sorted1 = sorted1.next;
}
}
}
使用
public class Test {
public static void main(String[] args) {
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.add(2);
myLinkedList1.add(4);
myLinkedList1.add(1);
MyLinkedList.Node<Integer> head1 = myLinkedList1.head;
MyLinkedList myLinkedList2 = new MyLinkedList();
myLinkedList2.add(9);
myLinkedList2.add(1);
myLinkedList2.add(3);
MyLinkedList.Node<Integer> head2 = myLinkedList2.head;
MyLinkedList.Node<Integer> sorted1 = myLinkedList1.sorted();
MyLinkedList.Node<Integer> sorted2 = myLinkedList2.sorted();
System.out.println("排序后的链表1:");
MyLinkedList.forEachPrint(sorted1);
System.out.println();
System.out.println("排序后的链表2:");
MyLinkedList.forEachPrint(sorted2);
MyLinkedList.Node<Integer> merge = myLinkedList1.merge(head1, head2);
System.out.println();
System.out.println("合并后的链表:");
MyLinkedList.forEachPrint(merge);
}
}