需求
思路
排序:讲所有的值都取出来,存储到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) ; } }