这段代码是如何导致dummy和L3列表的填充的?

huangapple go评论63阅读模式
英文:

How does this code lead to the populating of dummy and the L3 list as well?

问题

在这段代码中,我正在使用虚拟节点的概念。对于这个概念,我理解虚拟列表是如何被填充的,然而,我似乎无法理解L3列表是如何被填充的。我只是将其视为虚拟列表的初始化器。

例如,当代码第一次运行时,考虑L1(1 > 2 > 4)和L2(1 > 3 > 4)。当dummy.next语句运行时,它同时填充了dummy和L3。为什么会这样呢?

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode dummy = l3;
        
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                dummy.next = l1;
                l1 = l1.next;
            }
            else{
                dummy.next = l2;
                l2 = l2.next;
            }
            
            dummy = dummy.next;
        }
        
        return l3.next;   
    }
英文:

In this code, I am making use of the concept of dummy nodes. For this, I understand how the dummy list gets populated, however, I cannot seem to wrap my head around how the l3 list gets populated as well. I am just thinking of it as a initializer for the dummy list.

For instance, when the code runs for the first time, considering L1 (1 > 2 > 4) and L2 (1 > 3 > 4). When the dummy.next statement runs, it populates both the dummy and the L3. Why is that?

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode dummy = l3;
        
        while(l1 != null &amp;&amp; l2 != null){
            if(l1.val &lt;= l2.val){
                dummy.next = l1;
                l1 = l1.next;
            }
            else{
                dummy.next = l2;
                l2 = l2.next;
            }
            
            dummy = dummy.next;
        }
        
        return l3.next;   
    }

答案1

得分: 1

当dummy.next语句运行时,它同时填充了dummy和L3。为什么会这样?

当你将一个对象赋值给另一个对象时,你实际上在这两个对象的地址之间建立了一个链接(例如dummy和l3)。假设 -

你有一个对象A(地址1000);现在当你像下面这样将另一个对象赋值给它:

A = B

你实际上在名为B的对象中制作了一个对象A的副本(地址为1000)。现在这两个对象都指向RAM中的相同位置,无论你对一个对象进行了什么更改,它都会反映在另一个对象上。

我想你已经得到了你的答案。

额外提示:

你的代码中似乎存在一些问题,请调试以使其可接受。

英文:

> When the dummy.next statement runs, it populates both the dummy and the L3. Why is that?

when you are assigning one object to another, you making a link between both of these object's address (dummy and l3 for example). Assume -

You have object A (address 1000); now when you are assigning another object with it, like following :

> A = B

you are actually making a replica of object A, in the name of B (with address 1000). Now both the object pointing to the same location in RAM, whatever changes you will make on one object it will reflect on other as well.

I think you got your answer.

EXTRA:

you have some problem in your code, debug it to make it acceptable.

答案2

得分: 0

让我们通过一个示例来解释这个过程。假设我们有以下两个列表:

[L1-one | next] --> [L1-two | next] --> [L1-three | next] --> null
[L2-one | next] --> [L2-two | next] --> null

其中第一个“字段”反映了讨论的其余部分的某个唯一标识符,--> 反映了 next 引用。

现在算法从接收到两个列表 l1l2 开始作为参数:

  l1
   |
   v
[L1-one | next] --> [L1-two | next] --> [L1-three | next] --> null
[L2-one | next] --> [L2-two | next] --> null
   ^
   |
  l2

它为新列表创建一个虚拟节点,将其存储为 l3dummy

  l3, dummy
   |
   v
[L3-dummy | next] --> null

现在,根据 l1.val < l2.val 是否成立,要么将 l1 要么将 l2 设置为 dummy.next。假设 l1.val < l2.val,因此将 l1 设置为 dummy.next

  l3, dummy
   |
   v
[L3-dummy | next] --.
                    |
  l1  .-------------.
   |  |
   v  v
[L1-one | next] --> [L1-two | next] --> [L2-three | next] --> null

[L2-one | next] --> [L2-two | next] --> null
   ^
   |
  l2

接下来,将 l1 设置为 l1.next

  l3, dummy
   |
   v
[L3-dummy | next] --.
                    |
      .-------------. l1
      |                |
      v                v
[L1-one | next] --> [L1-two | next] --> [L1-three | next] --> null

[L2-one | next] --> [L2-two | next] --> null
   ^
   |
  l2

最后,在最后一步中,将 dummy 设置为 dummy.next

  l3
   |
   v
[L3-dummy | next] --.
                    |
dummy .-------------. l1
   |  |                |
   v  v                v
[L1-one | next] --> [L1-two | next] --> [L1-three | next] --> null

[L2-one | next] --> [L2-two | next] --> null
   ^
   |
  l2

迭代重新开始。现在假设 l1.val > l2.val。因此,将 dummy.next 设置为 l2,将 l2 设置为 l2.next,并将 dummy 设置为 dummy.next,结果如下:

  l3
   |
   v
[L3-dummy | next] --.
                    |
   .----------------. l1
   |                   |
   v                   v
[L1-one | next] --> [L1-two | next] --> [L1-three | next] --> null
                  |
   .--------------.
   |
   v
[L2-one | next] --> [L2-two | next] --> null
   ^                   ^
   |                   |
dummy                 l2

对于下一次迭代,假设 l1.value < l2.value。我们将以以下图表完成迭代:

  l3
   |
[L3-dummy | next] --.
                    |
   .----------------. l2                  l1
   |                   |                   |
   v                   v                   v
[L1-one | next] --> [L1-two | next] --> [L1-three | next] --> null
                  |    ^
   .--------------.    |
   |                   .--------------.
   v                                  |
[L2-one | next] --> [L2-two | next] --.
                       ^
                       |
                    dummy

其他迭代只会移动 l1l2dummy,但不会更改对象的结构。

现在注意,l3 仍然引用最初的虚拟头部,并且第一和第二个列表的某些引用已经更改。

英文:

Let us work through this one with an example. Say we have two lists as follows:

[L1-one | next] --&gt; [L1-two | next] --&gt; [L1-three | next] --&gt; null
[L2-one | next] --&gt; [L2-two | next] --&gt; null

Where the first "field" reflects some unique identifier for the rest of the discussion and --&gt; reflects the next-references.

Now the algorithm starts by receiving two lists l1 and l2 as parameters:

  l1
   |
   v
[L1-one | next] --&gt; [L1-two | next] --&gt; [L1-three | next] --&gt; null
[L2-one | next] --&gt; [L2-two | next] --&gt; null
   ^
   |
  l2

And it creates a dummy-node for the new list, stores it as l3 and dummy

  l3, dummy
   |
   v
[L3-dummy | next] --&gt; null

Now depending whether l1.val &lt; l2.val, either l1 or l2 will be set to dummy.next. Let us assume that l1.val &lt; l2.val, thus l1 is set as dummy.next:

  l3, dummy
   |
   v
[L3-dummy | next] --.
                    |
  l1  .-------------.
   |  |
   v  v
[L1-one | next] --&gt; [L1-two | next] --&gt; [L2-three | next] --&gt; null




[L2-one | next] --&gt; [L2-two | next] --&gt; null
   ^
   |
  l2

Next, l1 is set to l1.next:

  l3, dummy
   |
   v
[L3-dummy | next] --.
                    |
      .-------------. l1
      |                |
      v                v
[L1-one | next] --&gt; [L1-two | next] --&gt; [L1-three | next] --&gt; null




[L2-one | next] --&gt; [L2-two | next] --&gt; null
   ^
   |
  l2

Finally, in the last step, dummy is set to dummy.next:

  l3
   |
   v
[L3-dummy | next] --.
                    |
dummy .-------------. l1
   |  |                |
   v  v                v
[L1-one | next] --&gt; [L1-two | next] --&gt; [L1-three | next] --&gt; null




[L2-one | next] --&gt; [L2-two | next] --&gt; null
   ^
   |
  l2

The iteration starts again. Now let us assume that l1.val &gt; l2.val. Thus, dummy.next is set to l2, l2 is set to l2.next and dummy is set to dummy.next, resulting in the following image:

  l3
   |
   v
[L3-dummy | next] --.
                    |
   .----------------. l1
   |                   |
   v                   v
[L1-one | next] --. [L1-two | next] --&gt; [L1-three | next] --&gt; null
                  |
   .--------------.
   |
   v
[L2-one | next] --&gt; [L2-two | next] --&gt; null
   ^                   ^
   |                   |
dummy                 l2

And for the next iteration, let us assume that l1.value &lt; l2.value. We would finish the iteration with the following diagram:

  l3
   |
[L3-dummy | next] --.
                    |
   .----------------. l2                  l1
   |                   |                   |
   v                   v                   v
[L1-one | next] --. [L1-two | next] --&gt; [L1-three | next] --&gt; null
                  |    ^
   .--------------.    |
   |                   .--------------.
   v                                  |
[L2-one | next] --&gt; [L2-two | next] --.
                       ^
                       |                     
                    dummy

The other iterations will only move l1, l2 and dummy, but not change the structure of the objejcts.

Now notice that l3 is still referencing the initial dummy head and that some references from the first and second list has changed.

huangapple
  • 本文由 发表于 2020年8月23日 00:42:53
  • 转载请务必保留本文链接:https://go.coder-hub.com/63538661.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定