用Java实现两个有序链表合并

x33g5p2x  于2022-09-14 转载在 Java  
字(2.1k)|赞(0)|评价(0)|浏览(335)

合并两个有序链表问题

合并两个排序的链表并将其作为新列表返回。新列表也应该排序。

例子:

Input: 
1->2->4 
1->3->4

Output: 1->1->2->3->4->4

在 Java 中合并两个排序的链表解决方案

初始化一个表示合并列表 (result) 的新 LinkedList。现在,遍历两个列表(l1l2),并为每次迭代

  • 找到最小值的节点
  • 将此节点添加到合并列表(result

这是完整的实现:

class ListNode {
  int val;
  ListNode next;
  ListNode(int val) {
    this.val = val;
  }
}

class MergeSortedLinkedList {

  private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
    ListNode result = null;
    ListNode head = null;
    
    while(l1 != null || l2 != null) {
      int minVal;
      if (l1 == null) {
        minVal = l2.val;
        l2 = l2.next;
      } else if (l2 == null) {
        minVal = l1.val;
        l1 = l1.next;
      } else if(l1.val <= l2.val) {
        minVal = l1.val;
        l1 = l1.next;
      } else {
        minVal = l2.val;
        l2 = l2.next;
      }

      if(result == null) {
        result = head = new ListNode(minVal);
      } else {
        result.next = new ListNode(minVal);
        result = result.next;
      }
    }

    return head;
  }

  public static void main(String[] args) {
    ListNode l1 = new ListNode(1);
    l1.next = new ListNode(2);
    l1.next.next = new ListNode(4);

    ListNode l2 = new ListNode(1);
    l2.next = new ListNode(3);
    l2.next.next = new ListNode(4);

    ListNode mergedList = mergeSortedLinkedLists(l1, l2);
    while(mergedList != null) {
      System.out.print(mergedList.val + " ");
      mergedList = mergedList.next;
    }
    System.out.println();
  }
}
# Output
$ javac MergeSortedLinkedList.java
$ java MergeSortedLinkedList
1 1 2 3 4 4

请注意,我们正在为生成的链接列表创建新节点,而不是直接使用提供的链接列表的节点。此解决方案将使用额外空间,但建议在现实世界中使用,因为我们不会修改参数中提供的 LinkedLists。

如果您不想创建新节点,则可以直接使用提供的 LinkedList 节点:

private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
  ListNode result = null;
  ListNode head = null;
  
  while(l1 != null || l2 != null) {
    ListNode minNode;
    if (l1 == null) {
      minNode = l2;
      l2 = l2.next;
    } else if (l2 == null) {
      minNode = l1;
      l1 = l1.next;
    } else if(l1.val <= l2.val) {
      minNode = l1;
      l1 = l1.next;
    } else {
      minNode = l2;
      l2 = l2.next;
    }

    if(result == null) {
      result = head = minNode;
    } else {
      result.next = minNode;
      result = result.next;
    }
  }

  return head;  
}

使用递归在 Java 中合并两个排序的链表解决方案

您还可以使用递归来合并链表。以下函数显示了递归方法:

private static ListNode mergeSortedLinkedLists(ListNode l1, ListNode l2) {
    if(l1 == null) {
      return l2;
    } else if (l2 == null) {
      return l1;
    }

    ListNode result = null;
    if(l1.val <= l2.val) {
      result = new ListNode(l1.val);
      result.next = mergeSortedLinkedLists(l1.next, l2);
    } else {
      result = new ListNode(l2.val);
      result.next = mergeSortedLinkedLists(l1, l2.next);
    }
    return result;
  }

相关文章

微信公众号

最新文章

更多