合并两个链表而不重复

Question

给定两个排序的链表，其结果应该是没有重复的并集。

不允许创建新节点。
生成的列表将由原始列表的元素组成。

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

L1 -> 2 3 3 4 4 4 5

L2 -> 3 4 5 5 6 7

结果 -> 2 3 4 5 6 7

下面有我的解决方案，但是在 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 部分 以获得更简短的解决方案。

Try it online!

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

第 2 部分

可以注意到在我上面的代码中 l1 和 l2 部分代码是对称的，因此我通过使用 l[i] 而不是 l1 和 l2，其中索引 i 表示我们是使用 l1 (l[0]) 还是 l2 (l[1])。这是简化的代码：

Try it online!

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

合并两个链表而不重复

Merge two linked lists without duplicities

python

algorithm

linked-list

python-3.x

singly-linked-list