问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

    class ListNode {
        int value;
        ListNode next;
        public ListNode(int value) {
            this.value = value;
        }
        // 重写toString方法，使打印出来的东西比较正常
        @Override
        public String toString() {
            StringBuilder stringBuffer = new StringBuilder();
            stringBuffer.append(value+" ");
            ListNode node = next;
            while (node != null){
                stringBuffer.append(node.value+" ");
                node = node.next;
            }
            return stringBuffer.toString();
        }
    }
    public ListNode merge(ListNode list1,ListNode list2) {
        // 合并后的结果
        ListNode res = null;
        // 如果list1链表为空则返回list2
        if(list1 == null){
            return list2;
        }
        // 如果list2链表为空则返回list1
        if(list2 == null){
            return list1;
        }

        System.out.println("A链表 "+list1.toString());
        System.out.println("B链表 "+list2.toString());
        // 如果链表A的头节点小于B的节点，那么A的头节点将会是合并后的节点
        // 然后去合并剩余的节点
        // 链表B的头结点的值小于链表A的头结点的值,链表B的头结点是剩余结点的头结点,然后把这个结点和之前已经合并好的链表的尾结点链接起来
        if(list1.value <= list2.value){
            list1.next = merge(list1.next, list2);
            return list1;
        }else{
            list2.next = merge(list1, list2.next);
            return list2;
        }
        return res;
    }

有的时候还需要将链表反转，逆序输出:

    public ListNode reverse(ListNode node){
        if (node == null || node.next == null) {
            return node;// 若为空链或者当前结点在尾结点，则直接返回
        }
        //先反转后面的链表，走到链表的末端结点
        ListNode reHead = reverse(node.next);
        //再将当前节点设置为后面节点的后续节点
        node.next.next = node;
        node.next = null;
        return reHead;
    }