两个没有重复的链表的交集

Question

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

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

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

L1 -> 2 3 3 4 4 4 5

L2 -> 3 4 5 6 7

结果 -> 3 4 5

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

有什么简单的方法可以改变 IntersectionDestruct 函数不创建任何新节点的逻辑吗？

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 LLIntersection(a, b):
    head = tail = None

    while a and b:
        if a.data == b.data:
            if head is None:
                head = Node(a.data, head)
                tail = head
            else:
                tail.next = Node(a.data, tail.next)
                tail = tail.next

            a = a.next
            b = b.next

        # advance the smaller list
        elif a.data < b.data:
            a = a.next
        else:
            b = b.next
    return head

Answer 1

您的解决方案实际上并不能防止重复，如果您在两个列表中都有重复的数字，那么一起推进 a 和 b 会导致它们再次匹配，并且结果中出现重复项。

您应该将它们都提升到新编号，这样可以防止任何重复。

然后通过将 a 分配给列表并清除其下一个值来重用原始节点，这样它就不会泄漏到现有列表中。

def IntersectionUnique(a, b):
    head = tail = None

    while a and b:
        if a.data == b.data:
            if head is None:
                head = tail = a
            else:
                tail.next = a
                tail = a
            
            # Skip past all duplicates (careful for end of list!)
            while a.next and a.data == a.next.data:
                a = a.next
            while b.next and b.data == b.next.data:
                b = b.next

            # Advance to new values
            a = a.next
            b = b.next
            
            # Clear tail
            tail.next = None

        # advance the smaller list
        elif a.data < b.data:
            a = a.next
        else:
            b = b.next
    return head

由于这会覆盖来自 a 的节点上的下一个值，因此在这之后从 a 遍历列表将给出与使用该函数之前相同的结果，直到第一个相交的项目被下一个覆盖，然后将是相交的只有在那之后的值。

因此认为它已损坏，仅使用 return 值。

两个没有重复的链表的交集

Intersection of two linked lists without duplicities

algorithm

linked-list

python-3.x