Shuffle合并两个节点数相同的链表

Question

我有两个函数用于合并两个链表，假设它们具有相同数量的元素

第一个：

    def shuffle_merge(self, l1,l2):
        node1 = l1.head
        node2 = l2.head
        if not node1 and not node2:
            return
        self.head = node1
        
        self.head.next = node2
        
        temp = self.head.next
        t1 = node1.next
        t2 = node2.next
       
        
        while t1 and t2:
            temp.next = t1
            temp = temp.next
            t1 = t1.next
            temp.next = t2
            temp = temp.next
            t2= t2.next`

第二个功能：

    def shuffle_merge(self, list1, list2):
        if list1.head is None and list2.head is None:
            return
        self.head=list1.head
        curr1=list1.head.next  
        self.head.next=list2.head
        curr2=list2.head.next
        new=self.head.next
        while curr1 and curr2:
            new.next=curr1
            new=new.next
            curr1=curr1.next
            new.next=curr2
            new=new.next
            curr2=curr2.next

现在第二个似乎按预期工作，但第一个没有例如合并列表 3->2->5->8->9 和 6->9->4->8->4给我输出 3->6->4。但为什么？我认为这可能与指针的工作方式有关，但我不明白。

Answer 1

第一个版本的问题就在这一部分：

    self.head = node1
    
    self.head.next = node2
    
    temp = self.head.next
    t1 = node1.next

对

self.head.next

的赋值是对

node1.next

的赋值，因此当您执行

t1 = node1.next

时，它不是预期的节点引用。

让我们用两个具有三个节点的列表来可视化它。在执行上面引用的语句之前，我们有这样的：

           node1
            │
          ┌─┴─────────┐   ┌───────────┐   ┌───────────┐
          │ value: 3  │   │ val: 2    │   │ val: 5    │
          │ next: ────────┤ next: ────────┤ next: None│
          └───────────┘   └───────────┘   └───────────┘
self
┌─┴─────────┐
│ head: None│
└───────────┘
    
          ┌───────────┐   ┌───────────┐   ┌───────────┐
          │ value: 6  │   │ val: 9    │   │ val: 4    │
          │ next: ────────┤ next: ────────┤ next: None│
          └─┬─────────┘   └───────────┘   └───────────┘
            │
           node2

执行前两条语句后，我们得到：

           node1
            │
          ┌─┴─────────┐   ┌───────────┐   ┌───────────┐
          │ value: 3  │   │ val: 2    │   │ val: 5    │
        ┌─┤ next: ┐   │   │ next: ────────┤ next: None│
        │ └───────│───┘   └───────────┘   └───────────┘
self    │         │
┌─┴─────│───┐     │
│ head: ┘   │     │
└───────────┘     │
        ┌─────────┘
        │ ┌───────────┐   ┌───────────┐   ┌───────────┐
        │ │ value: 6  │   │ val: 9    │   │ val: 4    │
        └─┤ next: ────────┤ next: ────────┤ next: None│
          └─┬─────────┘   └───────────┘   └───────────┘
            │
           node2

...您会注意到值为 2 的节点是如何被孤立的：它不再可达。当执行最后两条语句时，

t1

引用了错误的节点：

           node1
            │
          ┌─┴─────────┐   ┌───────────┐   ┌───────────┐
          │ value: 3  │   │ val: 2    │   │ val: 5    │
        ┌─┤ next: ┐   │   │ next: ────────┤ next: None│
        │ └───────│───┘   └───────────┘   └───────────┘
self    │         │
┌─┴─────│───┐     │
│ head: ┘   │     │
└───────────┘     │
        ┌─────────┘
        │ ┌───────────┐   ┌───────────┐   ┌───────────┐
        │ │ value: 6  │   │ val: 9    │   │ val: 4    │
        └─┤ next: ────────┤ next: ────────┤ next: None│
          └─┬─────┬──┬┘   └───────────┘   └───────────┘
            │     │  │
          node2  t1 temp

要解决此问题，请将赋值给

t1

before 分配给

self.head.next

的语句，然后您将得到：

           node1           t1
            │               │
          ┌─┴─────────┐   ┌─┴─────────┐   ┌───────────┐
          │ value: 3  │   │ val: 2    │   │ val: 5    │
        ┌─┤ next: ┐   │   │ next: ────────┤ next: None│
        │ └───────│───┘   └───────────┘   └───────────┘
self    │         │
┌─┴─────│───┐     │
│ head: ┘   │     │
└───────────┘     │
        ┌─────────┘
        │ ┌───────────┐   ┌───────────┐   ┌───────────┐
        │ │ value: 6  │   │ val: 9    │   │ val: 4    │
        └─┤ next: ────────┤ next: ────────┤ next: None│
          └─┬────────┬┘   └───────────┘   └───────────┘
            │        │
          node2     temp

希望这能澄清这一点。