java - Java：合并两个排序的链表

Question

我开发了一个代码来合并 java 中两个已经排序的链表。

我需要以下帮助：

1. 如何在不使用 tempNode 的情况下保留合并列表的头节点的值？

2. 这段代码可以更好地优化吗？

   public static ListNode mergeSortedListIteration(ListNode nodeA, ListNode nodeB) {
      ListNode mergedNode ;
      ListNode tempNode ;      
   
   if (nodeA == null) {
       return nodeB;
     } 
     if (nodeB == null) {
       return nodeA;
     }     
   
   
   if ( nodeA.getValue() < nodeB.getValue())
   {
       mergedNode = nodeA;
       nodeA = nodeA.getNext();
   }
   else
   {
       mergedNode = nodeB;
       nodeB = nodeB.getNext();
   }
   
   tempNode = mergedNode; 
   
   while (nodeA != null && nodeB != null)
   {           
   
       if ( nodeA.getValue() < nodeB.getValue())
       {               
           mergedNode.setNext(nodeA);
           nodeA = nodeA.getNext();
       }
       else
       {
           mergedNode.setNext(nodeB);
           nodeB = nodeB.getNext();                
       }       
       mergedNode = mergedNode.getNext();
   }
   
   if (nodeA != null)
   {
       mergedNode.setNext(nodeA);
   }
   
   if (nodeB != null)
   {
       mergedNode.setNext(nodeB);
   }       
   return tempNode;
   }
   

Answer 1

有几种可能：

1) 不要使用mergedNode来跟踪前一个节点，而是使用nodeA.getNext().getValue()and nodeB.getNext().getValue()。您的算法将变得更加复杂，您将不得不处理一些边缘情况，但可以消除您的变量之一。

2) 使用双向链表，然后使用nodeA.getPrev().getValue()andnodeB.getPrev().getValue()代替mergedNode. 您还必须在这里处理边缘情况。

为了处理边缘情况，您必须保证您的引用不可能null在调用getPrev(), getNext()or之前出现getValue()，否则您将抛出异常。

请注意，上述修改略微牺牲了执行时间和（更重要的是）简单性以消除变量。任何收益都是微不足道的，开发人员的时间远比减少一两微秒的操作时间重要得多。

Answer 2

1：您必须保留第一个节点的记录，这意味着您必须将其存储在变量中，例如tempNode.

2：没有。这里没有太多需要优化的地方。这个过程很简单。