下面是2020年9月21日面试遇到的一道真实面试题。

题目

两个有序(顺序未知)单向链表合并为一个可指定为升序或降序的链表。
例如：
数组A：1，2，3，4，5，6，7，8
数组B：2，4，6，10
结果：1，2，2，3，4，4，5，6，6，7，8，10

解题思路

1. 首先考虑如何合并两个有序单向链表
   合并为一个升序链表，我们需要两个升序链表；合并为一个降序链表，则需要两个降序链表。
2. 然后，我们需要根据结果要求，调整已知链表顺序与结果指定的一致。
3. 要确定已知链表的顺序
   顺序包括：升序，降序和所有值相等的情况。所有值相等的情况既可以当做升序，也可以当做降序。
4. 如果已知链表顺序与结果指定的顺序相反，需要将已知链表进行倒置操作。

流程图

流程图

代码

//节点结构
class Node{
    private int val;
    private Node next;
}
//定义顺序性枚举，升序，降序，平序
enum Sort{
    ASC, DESC, EQ;
}
//判断顺序性
private Sort isWhatSort(Node head){
    if (null == head || null == head.next){
        return Sort.EQ;
    }
    while (head.next != null){
        int compare = head.val - head.next.val;
        if (compare > 0){
            return Sort.DESC;
        } else if (compare < 0){
            return Sort.ASC;
        }
        head = head.next;
    }
    return Sort.EQ;
}
//翻转链表
private Node reverseList(Node head){
    if (null == head || null == head.next){
        return head;
    }
    Node first = head, second = head.next, last;
    first.next = null;
    while (null != second){
        last = second.next;
        second.next = first;
        first = second;
        second = last;
    }
    return first;
}
//合并两个同序的链表
private Node merge2Lists(Node h1, Node h2, Sort sort){
    Sort s1 = isWhatSort(h1);
    Sort s2 = isWhatSort(h2);
    Node head = new Node(), tail = head;
    //降序合并
    if (Sort.DESC == sort){
        if (s1 == Sort.ASC){
            h1 = reverseList(h1);
        }
        if (s2 == Sort.ASC){
            h2 = reverseList(h2);
        }
        while (null != h1 && null != h2){
            if (h1.val >= h2.val){
                tail.next = h1;
                tail = tail.next;
                h1 = h1.next;
            } else {
                tail.next = h2;
                tail = tail.next;
                h2 = h2.next;
            }
        }
        if (null == h1){
            tail.next = h2;
        }
        if (null == h2){
            tail.next = h1;
        }
    }else if (Sort.ASC == sort){//升序合并
        if (s1 == Sort.DESC){
            h1 = reverseList(h1);
        }
        if (s2 == Sort.DESC){
            h2 = reverseList(h2);
        }
        while (null != h1 && null != h2){
            if (h1.val >= h2.val){
                tail.next = h2;
                tail = tail.next;
                h2 = h2.next;
            } else {
                tail.next = h1;
                tail = tail.next;
                h1 = h1.next;
            }
        }
        if (null == h1){
            tail.next = h2;
        }
        if (null == h2){
            tail.next = h1;
        }
    }
    return head.next;
}