算法 剑指offer

剑指 Offer 25. 合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

1. 迭代，申明两个变量，一个作为最终输出结果，另一个负责遍历中重新组合链表。判断 l1 和 l2 元素大小，将小的节点赋值给 cur 并且该链表和 cur 后移一位，直到 l1 和 l2 其中一个为空循环结束。接着需要将未遍历完的链表拼接到 cur 上：cur.next = l1 == null ? l2 : l1。最终返回 result.next。
2. 递归，l1 <= l2 时 l1 入栈，反之 l2 入栈，所有元素入栈后出栈，将出栈结果赋值给 l1.next 或 l2.next 并返回相应的 l1 或 l2 即为最终结果。

代码

解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode result = new ListNode(0), cur = result;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 == null ? l2 : l1;
        return result.next;
    }
}

解法二

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

变形

要求对链表进行去重

解题思路

当 val 相等时：

1. 迭代直接跳过
2. 递归，需要将其中一个链表中重复的跳过，直接递归另一个链表的 next 即可

代码

解法一

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0), curr = node;
        while (l1 != null && l2 != null) {
            if (l1.val == l2.val) {
                ListNode tmp1 = l1;
                while (tmp1.next != null && tmp1.val == tmp1.next.val) tmp1 = tmp1.next;
                curr.next = tmp1;
                l1 = tmp1.next;
                ListNode tmp2 = l2;
                while (tmp2.next != null && tmp2.val == tmp2.next.val) tmp2 = tmp2.next;
                l2 = tmp2.next;
            } else if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        return node.next;
    }
}

解法二

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val == l2.val) {
            ListNode node = l1;
            while (node.next != null && node.val == node.next.val) {
                node = node.next;
            }
            l1 = node;
            l2 = mergeTwoLists(l1, l2.next);
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

本文由 Meridian 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Feb 26,2022