美文网首页
《剑指offer第二版》面试题25:合并连个排序的链表(java

《剑指offer第二版》面试题25:合并连个排序的链表(java

作者: castlet | 来源:发表于2020-04-04 12:54 被阅读0次

题目描述

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

解题思路:

  1. 因为链表都是递增排序的,可以分别比较链表当前节点的大小,较小的作为新链表的节点,再继续遍历剩下的节点。
  2. 当其中一个链表遍历到最后的时候,新链表的尾节点直接指向另一个不为null的链表即可。

代码

Listnode merge(Listnode head1, Listnode head2){
    if (head1 == null) {
        return head2;
    }
    if (head2 == null) {
        return head1;
    }

    // 找到头结点
    Listnode newHead = null;
    Listnode curHead = null;
    if (head1.value < head2.value) {
        newHead = head1;
        curHead = head1;
        head1 = head1.next;
    } else {
        newHead = head2;
        curHead = head2;
        head2 = head2.next;
    }

    // 合并2个链表
    while (head1 != null && head2 != null) {
        if (head1.value < head2.value) {
            curHead.next = head1;
            head1 = head1.next;
        } else {
            curHead.next = head2;
            head2 = head2.next;
        }
        curHead = curHead.next;
    }

    // 合并剩下的一个不为null的链表
    if (head1 != null) {
        curHead.next = head1;
    } else if (head2 != null) {
        curHead.next = head2;
    }
    return newHead;
}

相关文章

网友评论

      本文标题:《剑指offer第二版》面试题25:合并连个排序的链表(java

      本文链接:https://www.haomeiwen.com/subject/dtzdphtx.html