Java：合并两个已排序的链接列表

I have developed a code to merge two already sorted linked lists in java.

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

I need help with the following:

我需要以下方面的帮助:

How do I retain the value of head node of merged list without using tempNode?

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

Can this code be better optimized?

这段代码可以更好地优化吗?

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;
}

2 个解决方案

#1

1: You have to keep a record of the first node, which means you will have to store it in a variable such as tempNode.

1:您必须保留第一个节点的记录,这意味着您必须将其存储在诸如tempNode之类的变量中。

2: No. There's not much to optimize here. The process is quite trivial.

2:不。这里没有太多优化。这个过程非常简单。

#2

There are a few possibilities:

有几种可能性:

1) Instead of using mergedNode to keep track of the previous node, use nodeA.getNext().getValue() and nodeB.getNext().getValue(). Your algorithm will become more complex and you will have to deal with a few edge cases, but it is possible to eliminate one of your variables.

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

2) Use a doubly linked-list, and then use either nodeA.getPrev().getValue() and nodeB.getPrev().getValue() instead of mergedNode. You will also have to deal with edge cases here too.

2)使用双向链表,然后使用nodeA.getPrev()。getValue()和nodeB.getPrev()。getValue()而不是mergedNode。你也必须在这里处理边缘情况。

In order to deal with edge cases, you will have to guarantee that your references can not possibly be null before calling getPrev(), getNext() or getValue(), or else you will throw an exception.

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

Note that the above modifications sacrifice execution time slightly and (more importantly) simplicity in order to eliminate a variable. Any gains would be marginal, and developer time is far more important than shaving a microsecond or two off of your operation.

注意,为了消除变量,上述修改略微牺牲了执行时间并且(更重要的是)简单性。任何收益都是微不足道的,而且开发人员的时间远比削减一两微秒的操作更重要。

#1