合并两个无重复的链表

Question

给定两个已排序的链表，其中的结果应为并集，不重复。

• 不允许创建新节点

输入是两个由空行分隔的列表：

L1级-

L2级-

结果-

下面是我的解决方案，但在Union函数中创建新节点。

有没有什么简单的方法可以通过不创建任何新节点并删除重复节点的逻辑来更改Union函数？

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

def PrintLinkedList( p ):
    print( "Result:", end=" " )
    while p!=None:
        print( p.data, end=" " )
        p = p.next
    print(".")

def ReadLinkedList():
    first = None
    last = None
    r = input()
    while r!="":
        row = r.split()
        if len(row)==0:
            break
        for s in row:
            p = Node(int(s),None)
            if first==None:
                first = p
            else:
                last.next = p
            last = p
        r = input()
    return first

def dedup(head):
    current = head
    while current:
        runner = current
        # Check, until runner.next is not None.
        while runner.next:
            if current.data == runner.next.data:
                runner.next = runner.next.next
            else:
                runner = runner.next
        current = current.next

def Union(a, b):

    # A dummy node to store the result
    dummyNode = Node(0)
    headA = a
    headB = b

    # Tail stores the last node
    tail = dummyNode
    while True:

        # If any of the list gets completely empty
        # directly join all the elements of the other list
        if headA is None:
            tail.next = headB
            break
        if headB is None:
            tail.next = headA
            break

        # Compare the x of the lists and whichever is smaller is
        # appended to the last of the merged list and the head is changed
        if headA.data <= headB.data:
            tail.next = headA
            headA = headA.next
        else:
            tail.next = headB
            headB = headB.next

        # Advance the tail
        tail = tail.next

    # Delete dups and returns the head of the merged list
    dedup(dummyNode.next)
    return dummyNode.next

Answer 1

第1部分

在不修改您的解决方案的情况下，我决定实现我自己的解决方案，它不会创建任何新的节点。它执行常规的合并排序算法。有关更短的解决方案，请参阅我答案的第2部分。

在线试用！

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

def create_list(l):
    n = None
    for e in reversed(l):
        n = Node(e, n)
    return n

def print_list(l):
    if l is None:
        return
    else:
        print(l.data, end = ' ')
        print_list(l.next)

def main():
    l1, l2 = [list(map(int, input().split())) for i in range(2)]
    l1, l2 = create_list(l1), create_list(l2)
    
    r = None
    head = None
    last = None
    
    while True:
        if l1 is None and l2 is None:
            break
        
        if l2 is None or l1 is not None and l1.data <= l2.data:
            if last is None or last < l1.data:
                if r is None:
                    r = l1
                    head = r
                else:
                    r.next = l1
                    r = r.next
            last = l1.data
            l1 = l1.next
        elif l1 is None or l2.data < l1.data:
            if last is None or last < l2.data:
                if r is None:
                    r = l2
                    head = r
                else:
                    r.next = l2
                    r = r.next
            last = l2.data
            l2 = l2.next

    print_list(head)
            
main()

输入：

2 3 3 4 4 4 5
3 4 5 5 6 7

输出：

2 3 4 5 6 7

第二部分

我们可以注意到，在我上面的代码中，l1和l2部分代码是对称的，因此我使用l代码而不是l1和l2代码使代码更加简单（更短），其中索引I表示我们是否使用l1代码（<代码>l代码>）或l2代码（<代码>l代码>）。以下是简化代码：

在线试用！

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

def create_list(l):
    n = None
    for e in reversed(l):
        n = Node(e, n)
    return n

def print_list(l):
    if l is not None:
        print(l.data, end = ' ')
        print_list(l.next)

def main():
    l = [create_list(list(map(int, input().split()))) for i in range(2)]
    r, head, last = [None] * 3
    
    while l[0] is not None or l[1] is not None:
        i = [1, 0][l[1] is None or l[0] is not None and l[0].data <= l[1].data]
        if last is None or last < l[i].data:
            if r is None:
                r = l[i]
                head = r
            else:
                r.next = l[i]
                r = r.next
        last = l[i].data
        l[i] = l[i].next
    
    print_list(head)
            
main()

Answer 2

我建议单独处理第一个节点，这样您就知道合并列表的头部是什么。其余代码可以保持不变：

def Union(a, b):
    if a is None or b is None:  # Deal with this trivial case
         a = a or b
         dedup(a)
         return a

    headA = a
    headB = b

    # Tail stores the last node: process first node
    if headA.data <= headB.data:
        tail = headA
        headA = headA.next
    else:
        tail = headB
        headB = headB.next
    head = tail  # Remember what the head is of the merged list
    while True:
        if headA is None:
            tail.next = headB
            break
        if headB is None:
            tail.next = headA
            break
        if headA.data <= headB.data:
            tail.next = headA
            headA = headA.next
        else:
            tail.next = headB
            headB = headB.next

        # Advance the tail
        tail = tail.next

    # Delete dups and returns the head of the merged list
    dedup(head)
    return head