java-链表排序

需求

思路

• 排序：讲所有的值都取出来，存储到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 存放数据
        List<E> list = new ArrayList<>();
        while (head != null) {
            list.add(head.data);
            head = head.next;
        }

        //对list进行排序
        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;

        //功能1：对两个链表排序，并且分别遍历输出
        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);

        //功能2：合并两个有序链表，合并后的链表依然有序，并且遍历输出
        MyLinkedList.Node<Integer> merge = myLinkedList1.merge(head1, head2);
        // 遍历输出
        System.out.println();
        System.out.println("合并后的链表：");
        MyLinkedList.forEachPrint(merge);


    }


}