为什么这个 ‘b’ 链表发生了变化?

huangapple 未分类评论46阅读模式
英文:

Why does this 'b' linked list changed?

问题

我有两个链表:

'a':1->2->3->null

'b':4->5->null

我想将它们合并在一起:1->4->2->5->3->null

我编写了一个函数:

    private void merge(ListNode a, ListNode b){
        ListNode cur = new ListNode(0);
        
        while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next;
            a=a.next;
        }
        if(a==null && b==null) return;
        else if(a==null){
            cur.next = b;
        }else if(b==null){
            cur.next = a;
        }
        return;
    }

我认为的方法是使用一个'cur'变量来记录这两个链表'a'和'b'中的每个节点。然后这两个链表'a'和'b'分别移到它们的下一个节点。然后进入下一个WHILE循环。

然而,这是错误的。在我调试时,在这个第一个WHILE循环中,当它完成这个

cur.next = b;

时,变量将会改变如下:

a: [1,5,4]
b: [5,4]
cur: [1,5,4]

我很困惑为什么' a '链表会变成[1,5,4]?我认为在这一点上' a '链表不会改变,它保持为[1,2,3]。

-------- 但是当我将WHILE循环更改为以下内容时,它可以正常工作:

    while(a != null && b != null){
            cur.next = a;
            a=a.next;
            cur = cur.next;
            cur.next = b;
            b=b.next;
            cur = cur.next;
        }

所以我的问题是:
这两个WHILE循环之间有什么区别?

    while(a != null && b != null){
            cur.next = a;
            a=a.next;
            cur = cur.next;

            cur.next = b;
            b=b.next;
            cur = cur.next;
        }
while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next;
            a=a.next;
        }
英文:

I have 2 linked lists:

'a': 1->2->3->null

'b': 4->5->null

I want to merge them together as : 1->4->2->5->3->null

I write a function:

    private void merge(ListNode a, ListNode b){
        ListNode cur = new ListNode(0);
        
        while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next;
            a=a.next;
        }
        if(a==null && b==null) return;
        else if(a==null){
            cur.next = b;
        }else if(b==null){
            cur.next = a;
        }
        return;
    }

what I think is to use a 'cur' to record each node in these 2 linked list 'a' and 'b'. Then these 2 linked lists 'a' and 'b' move to its next node. Then go to the next WHILE loop.

However, it's wrong. When I debug, in this first WHILE loop, when it finished this

cur.next = b;

it shows that variables will change as follow:

a: [1,5,4]
b: [5,4]
cur: [1,5,4]

I'm so confused why 'a' linked list will change to [1,5,4]? I think 'a' linked list won't change at this point, it keeps as [1,2,3].

--------But when I change WHILE loop as this following, it works:

    while(a != null && b != null){
            cur.next = a;
            a=a.next;
            cur = cur.next;
            cur.next = b;
            b=b.next;
            cur = cur.next;
        }

So my question is:
what's the difference between these two WHILE loop?

    while(a != null && b != null){
            cur.next = a;
            a=a.next;
            cur = cur.next;

            cur.next = b;
            b=b.next;
            cur = cur.next;
        }
while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next;
            a=a.next;
        }

答案1

得分: 0

当“cur”指向一个其下一个节点仍然需要的节点时,仍然无法赋值给next。

在方法末尾使用return;是不必要的。

首先使用递归可能会有所帮助,先完成一小部分简单的工作,然后调用相同方法的其他实例来处理其余部分。

递归版本如下:

private ListNode merge(ListNode a, ListNode b) {
    if (a == null) {
        return b;
    } else if (b == null) {
        return a;
    }
    ListNode anext = a.next;
    a.next = merge(b, a.next);
    return a;
}

可以改写为迭代版本:

private ListNode merge(ListNode a, ListNode b) {
    while (true) {
        if (a == null) {
            return b;
        } else if (b == null) {
            return a;
        }
        ListNode anext = a.next;
        a.next = b;

        a = b;
        b = anext;
    }
}

这种方法可以处理长度不同的链表,因此需要一个结果。

难点在于,与其执行a.next和b.next两步,而是调换了函数调用的参数。

你的版本将结果放在“a”中,并且要求两个链表具有相同的长度。
a为空,而b不为空是不可能的。

在你的第一个版本中,首先引入了一个0元素。

英文:

The problem that when cur points to a node whose next is still needed you still cannot assign to next.

Tip at the end of a method return; is not needed.

It may help to first use recursion, doing an easy bit of work, and call other instances of the same method for the rest.

A recursion would be:

private ListNode merge(ListNode a, ListNode b) {
    if (a == null) {
        return b;
    } else if (b == null) {
        return a;
    }
    ListNode anext = a.next;
    a.next = merge(b, a.next);
    return a;
}

which becomes iterative:

private ListNode merge(ListNode a, ListNode b) {
    while (true) {
        if (a == null) {
            return b;
        } else if (b == null) {
            return a;
        }
        ListNode anext = a.next;
        a.next = b;

        a = b;
        b = anext;
    }
}

This handles lists with different lengths, and hence needs a result.

The difficult point is that instead of taking two steps a.next and b.next the call's arguments are switched.

Your version puts the results in a and requires that both lists have the same length.
a being null and b not so would not be possible.

In your first version a 0 element is first introduced.

答案2

得分: 0

在你的 while 循环中存在一个 bug。对于一个正确的合并算法,你的循环不变式应该位于 while 循环的每次迭代结束时,ListNode a 和 b 应该指向它们各自列表中的下一个元素。

while(a != null && b != null){
    cur.next = a;
    cur = cur.next;
         
    cur.next = b;
    cur = cur.next;
                
    b = b.next; 
    a = a.next; // 你把 a 指向了列表 b 中的节点,这是错误的。
}

根据你的测试数据

列表 a:1 -> 2 -> 3
列表 b:4 -> 5

让我们在第一次迭代后检查你的 while 循环不变式

(i) a = a.next 将 a 设置为 b 中的第一个节点,即 4,但它应该指向其自己列表中的下一个元素 1 -> 2 -> 3,即 2

这破坏了你的算法。

英文:

Yes there is a bug in your while loop . For a correct merge algorithm your loop invariant should be at the end of each iteration in the while loop ListNode a and b should point to next element in their respective list .

while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next; 
            a=a.next; // you are making a point to node in list b , which is wrong .
        }

From your test data

List a : 1 -> 2 -3
List b : 4 -> 5

Lets check the invariant of your while loop after 1st iteration

(i) a=a.next sets a to first node in b i.e 4 whilst it should point to next element in its own list 1->2->3 i.e 2

This breaks your algorithm.

huangapple
  • 本文由 发表于 2020年7月27日 03:23:53
  • 转载请务必保留本文链接:https://java.coder-hub.com/63104675.html
匿名

发表评论

匿名网友

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

确定