本文共 2538 字，大约阅读时间需要 8 分钟。

链表不降序合并的优化思路

合并两个单调递增的链表，生成一个新的链表，使得新链表同样遵循单调递增规则。以下是两种常见方法：迭代法和递归法。

迭代法

思路:

代码示例：

class ListNode {    int val;    ListNode next;    public ListNode(int val) {        this.val = val;    }}public class Solution {    public ListNode Merge(ListNode list1, ListNode list2) {        if (list1 == null) {            return list2;        }        if (list2 == null) {            return list1;        }        ListNode newHead = new ListNode(-1);        ListNode cur = newHead;        while (list1 != null && list2 != null) {            if (list1.val <= list2.val) {                cur.next = list1;                list1 = list1.next;            } else {                cur.next = list2;                list2 = list2.next;            }            cur = cur.next;        }        while (list1 != null) {            cur.next = list1;            list1 = list1.next;            cur = cur.next;        }        while (list2 != null) {            cur.next = list2;            list2 = list2.next;            cur = cur.next;        }        return newHead.next;    }}

递归法

思路:

代码示例：

public class Solution {    public ListNode Merge(ListNode list1, ListNode list2) {        if (list1 == null) {            return list2;        }        if (list2 == null) {            return list1;        }        ListNode newHead;        if (list1.val <= list2.val) {            newHead = list1;            list1 = list1.next;        } else {            newHead = list2;            list2 = list2.next;        }        list1 = list1 != null ? list1.next : null;        list2 = list2 != null ? list2.next : null;        return Merge(newHead, list1, list2);    }    private static ListNode Merge(ListNode head1, ListNode head2, ListNode next1, ListNode next2) {        if (head1 == null) {            return head2;        }        if (head2 == null) {            return head1;        }        // 比较当前节点，决定将哪个接入结果        if (head1.val <= head2.val) {            return new MergeNode(head1, head2, head1.next, head2.next, next1, next2);        } else {            return new MergeNode(head2, head1, head2.next, head2.next, next1, next2);        }    }    // 选项：可以根据具体需求调整节点构建方式，避免担心head1和head2被修改    // 更常见的实现可能使用引用而非创造新节点

实现总结

两种方法各有优劣：迭代法直观，性能较好；递归法代码简洁，但需谨慎处理栈深度问题。推荐根据项目规模选择合适方法。

转载地址：http://gjsgz.baihongyu.com/