Python 单链表合并输出缺失值

Question

目前我正在学习如何合并两个单链表；但是，我似乎无法理解为什么当我输入值时它缺少第一个值。

这是我的 class..

class SinglyListNode:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

这是我使用的合并代码：

def mergeList(self, list):
    p = self.head 
    q = list.head
    s = None

    if not p:
        return q
    if not q:
        return p

    if p and q:
        if p.data <= q.data:
            s = p 
            p = s.next
        else:
            s = q
            q = s.next
        new_head = s 

    while p and q:
        if p.data <= q.data:
            s.next = p 
            s = p 
            p = s.next
        else:
            s.next = q
            s = q
            q = s.next
    if not p:
        s.next = q 
    if not q:
        s.next = p 
    return new_head

这些是数组中的数字

  array1 = [ 3, 6, 6, 10, 45, 45, 50] ; 
  array2 = [2, 3, 55, 60 ]

这些是打印代码：

def printList(self):
    temp = self.head
    print "[",
    while temp is not None:
        print temp.data,
        temp = temp.next
    print "]"

s1.mergeList(s2)
print "Content of merged list"
s1.printList()

输出是...

[ 3 3 6 6 10 45 45 50 55 60 ]

本例中的值 2 没有被打印出来。我试图在 mergeList 中打印 new_head 头部的值，我得到了 2.

我不明白的是为什么打印的时候，列表头部的2的值消失了。

感谢您的帮助。

Answer 1

将您的代码归结为重要部分，我们有：

class SinglyLinkedList:
    #...
    def mergeList(self, list):
        p = self.head 
        q = list.head
        s = None

        #...

        if p and q:
            if p.data <= q.data:
                s = p 
                p = s.next
            else:
                s = q
                q = s.next
            new_head = s

            #...

            return new_head

    #...

    s1.mergeList(s2)
    print "Content of merged list"
    s1.printList()

在合并两个列表时（据我所知，此函数中的逻辑是正确的），您定义了一个名为 new_head 的变量，然后 return 它。

但是当你调用函数时：

s1.mergeList(s2)

你"throw away"的return值。但是这个 return 值是合并列表的头部，所以如果 list [1] 的第一个元素小于 self 的第一个元素，打印 s1将开始一个元素 "late".

相反，请考虑更改以下内容：

return new_head

至

self.head = new_head

您将看到列表按预期打印。

[1] 您可以在此处考虑使用不同的变量名称，以避免隐藏内置 list 类型。

Python 单链表合并输出缺失值

Python missing value in output of Singly-linked list merge

python

oop

linked-list

singly-linked-list