有序链表的合并

import cn.leekari.base.ListNode;

/**
 * @author leekari
 * @date 2020/10/15 09:52
 * @description
 */

/**
 * 有序链表的合并
 */
public class MergeTwListNode {
    /**
     * 递归实现有序链表合并
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeList(ListNode l1, ListNode l2){
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode listNode = new ListNode();

        if (l1.val >= l2.val){
            listNode = l2;
            listNode.next = mergeList(l1, l2.next);
        }else {
            listNode = l1;
            listNode.next = mergeList(l1.next, l2);
        }
        return listNode;
    }

    /**
     * 非递归实现有序链表合并
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeList2(ListNode l1, ListNode l2){
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode listNode = new ListNode(0);
        //使用临时listNode来拼接
        ListNode tempListNode = listNode;
        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                tempListNode.next = l2;
                l2 = l2.next;
            }else {
                tempListNode.next = l1;
                l1 = l1.next;
            }
            tempListNode = tempListNode.next;
        }
        //链表，直接将剩余元素的根结点挂上去
        if (l1 != null){
            tempListNode.next = l1;
        }
        if (l2 != null){
            tempListNode.next = l2;
        }

        return listNode.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode();
        l1.val = 1;
        l1.next = new ListNode();
        l1.next.val = 3;
        l1.next.next = new ListNode();
        l1.next.next.val = 5;
//        ListNode l2 = new ListNode();
//        l2.val = 2;
//        l2.next = new ListNode();
//        l2.next.val = 4;
//        l2.next.next = new ListNode();
//        l2.next.next.val = 6;
        ListNode l2 = new ListNode(0);
        ListNode l = mergeList2(l1, l2);
        while (l != null){
            System.err.println(l.val);
            l = l.next;
        }
    }
}