在 java 中使用内置的 LinkedList 而不是定义 ListNode

Question

我想合并两个排序的链表（21 leetcode）但我不想定义 ListNode。我需要使用用 Java 定义的 LinkedList，我认为它的方法足以解决有关它的任何问题。 （我是 leetcode 的新手，我不知道为什么 ListNode 定义在 leetcode 代码的顶部，而我们已经在 Java 中有了它）。无论如何，我创建了两个链表并对它们进行了排序。现在我需要创建另一个节点作为 tempNode 和 currentNode 来合并这两个排序的链表。你能帮我吗？

ListNode temp_Node= new ListNode(0);

ListNode current_Node= temp_Node;
 

我也不知道如何使用 val like

while(list1!=null && list2!=null){
            if (list1.val<list2.val){
              current_Node.next= list1;
              list1=list1.next;

你能帮帮我吗？这是我的代码。

package MergeTwoSortedLists;

     import java.util.ArrayList;
     import java.util.Arrays;
     import java.util.Collections;
     import java.util.Comparator;
     import java.util.LinkedList;
     import java.util.Scanner;

     public class Driver
     {
         public static void main(String[] args)
        {
          Scanner scanner= new Scanner(System.in);
          String str1= scanner.nextLine();
          String str2= scanner.nextLine();
       
          String[] str_arr1=str1.split(" ");;
          String[] str_arr2=str2.split(" ");`
          LinkedList<String> lnk_List3= new LinkedList<String>();
          LinkedList<String> lnk_List4= new LinkedList<String>();
          for (int i=0; i<str_arr1.length; i++) {
             lnk_List3.add(str_arr1[i]);
          }
          for(int i=0; i<str_arr2.length; i++) {
            lnk_List4.add(str_arr2[i]);
          }
          Collections.sort(lnk_List1);
          Collections.sort(lnk_List2);
       }
     }

谢谢。

Answer 1

很简单， 如果您的输入是对链表进行排序，则使用合并算法（不是合并排序，只是合并算法）对两个链表进行排序。

https://www.geeksforgeeks.org/merge-two-sorted-linked-lists/

合并算法将两个列表（在您的情况下）排序为 O(m+n) 时间复杂度的单个列表。你正在做的事情需要 O(mlogm + nlogn + m + n)

因此使用合并算法并提高效率。

快乐编码:)

leet Code 是一个让你从基础开始练习的平台。 他们想教指针并将算法与这个问题结合起来。