Вставка общих элементов из двух связанных списков в третий связанный список

Question

Я нашел свое решение ... спасибо за помощь!

Answer 1

Проблема в методе intersection (), где вы повторно инициализируете current_node3. Ниже приведено исправление для того же

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

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

def sortedinsert(self, data):
    current_node = self.head
    if current_node==None:
        new_node = Node(data)
        self.head = new_node
        return
    if current_node.data > data:
        new_node = Node(data)
        new_node.next = current_node
        self.head = new_node
        return
    while current_node.next is not None:
        if current_node.next.data > data:
            break
        current_node = current_node.next
    new_node = Node(data)
    new_node.next = current_node.next
    current_node.next = new_node
    return

def delete(self, item):
    current_node = self.head
    if current_node and current_node.data == item:
        self.head = current_node.next
        current_node = None
        return
    previous_node = None
    while current_node and current_node.data != item:
        previous_node = current_node
        current_node = current_node.next
    if current_node is None:
        return
    previous_node.next = current_node.next
    current_node = None

def deletebefore(self, value):
    current_node = self.head
    previous_node = None

    if current_node.data == value:
        print("There is no previous character")
        return

    while current_node.next.data != value:
        previous_node = current_node
        current_node = current_node.next
        if current_node.next == None:
            print("Given character not found")
            return

    if previous_node == None and current_node.next.data == value:
        self.head = current_node.next
        current_node = None
        return

    if current_node.next.data == value and previous_node:
        previous_node.next = current_node.next
        current_node = None

def update(self, prev_value, new_value):
    new_value=Node(new_value)
    current_node = self.head
    while current_node.data != prev_value:
        current_node = current_node.next
    if current_node.data == prev_value:
        current_node.data = new_value.data
        return

def isempty(self,l1,l2,l3):
    current_node = self.head
    if current_node is None:
        print("List is empty")

    else:
        print("List is not Empty")

def getsize(self):
    items = []
    present_node = self.head
    while present_node is not None:
        items.append(present_node.data)
        present_node = present_node.next
    print(len(items))

def getfirst(self):
    current_node = self.head
    if current_node:
        print(current_node.data)

def intersection(self,l1,l2):
    if l1==None and l2==None:
        print("Linked lists are empty")
    current_node = l1.head
    current_node2 = l2.head
    current_node3=self.head
    while current_node2!=None:
        if current_node2.data==current_node.data:
            if current_node3 is None:
                current_node3=current_node2 # Here is the problem. You are reinitializint the node. So, it no more points to head node
                self.head = current_node2 # Fix : set head to node 3 again
                if current_node2.next==None:
                    return
                else:
                    current_node2=current_node2.next
                    current_node=current_node.next
            else:
                while current_node3!=None:
                    current_node3=current_node3.next
                current_node3=current_node2
                current_node2=current_node2.next
                current_node=current_node.next

        else:
            current_node=current_node.next
            if current_node==None:
                current_node=l1.head
                current_node2=current_node2.next

def display(self):
    current_node=self.head
    while current_node!=None:
        print(current_node.data)
        current_node=current_node.next
def main():
l1 = LinkedList()
l2 = LinkedList()
l3 = LinkedList()
l1.sortedinsert(19)
l1.sortedinsert(16)
l2.sortedinsert(19)
l2.sortedinsert(15)
l2.sortedinsert(16)
l3.intersection(l1,l2)


def intersection(self,l1,l2):
        if l1==None and l2==None:
            print("Linked lists are empty")
        current_node = l1.head
        current_node2 = l2.head
        current_node3=self.head
        while current_node2!=None:
            if current_node2.data==current_node.data:
                if current_node3 is None:
                    current_node3=current_node2 
                    if current_node2.next==None:
                        return
                    else:
                        current_node2=current_node2.next
                        current_node=current_node.next
                else:
                    while current_node3!=None:
                        current_node3=current_node3.next
                    current_node3=current_node2
                    current_node2=current_node2.next
                    current_node=current_node.next

            else:
                current_node=current_node.next
                if current_node==None:
                    current_node=l1.head
                    current_node2=current_node2.next

def main():
    l1 = LinkedList()
    l2 = LinkedList()
    l3 = LinkedList()
    l1.sortedinsert(19)
    l1.sortedinsert(16)
    l2.sortedinsert(19)
    l2.sortedinsert(15)
    l2.sortedinsert(16)
    l3.intersection(l1,l2)
    node = l1.head

    #Print all 3 linked list
    print('List 1')
    l1.display()

    node = l2.head
    print('List 2')
    l2.display()

    node = l3.head
    print('List 3')
    l3.display()


main()

Модифицирующего метода пересечения

def intersection(self,l1,l2):
    if l1==None and l2==None:
        print("Linked lists are empty")
    current_node = l1.head
    current_node2 = l2.head

    while current_node2!=None:
        if current_node2.data==current_node.data:
            self.sortedinsert(current_node2.data)
            current_node2=current_node2.next
            current_node=current_node.next
        else:
            current_node=current_node.next
            if current_node==None:
                current_node=l1.head
                current_node2=current_node2.next

Answer 2

Во-первых, вы хотите убедиться, что если связанные списки имеют повторяющиеся общие значения, например [1, 2, 2, 3] и [0, 2, 2, 3], они не отображаются в пересечении дублируется, т.е. результат должен быть [2, 3]. Во-вторых, пересечение должно делать копии узлов на случай, если обновление выполнено для узла в одном из входных списков. Также может показаться, что ваш метод update потенциально оставит ваш LinkedList несортированным.

def intersection(self, l1, l2):
    """
    This assumes both lists are sorted. This assumption may not be true due
    to method update possibly leaving list unsorted.
    """
    assert l1 and l2 # We assume people are passing us valid lists, which may be empty
    self.head = None # to start out empty
    last_node = None
    current_node_1 = l1.head
    current_node_2 = l2.head
    while current_node_1 and current_node_2:
        if current_node_1.data > current_node_2.data:
            current_node_1, current_node_2 = current_node_2, current_node_1 # if one is larger, make it current_node_2
        if current_node_1.data < current_node_2.data:
            current_node_1 = current_node_1.next
            continue
        # must be equal:
        last_data = current_node_1.data
        new_node = Node(last_data)
        if last_node is None:
            self.head = new_node
        else:
            last_node.next = new_node
        last_node = new_node
        while current_node_1 and current_node_1.data == last_data: # in case this value is not unique in the list
            current_node_1 = current_node_1.next
        while current_node_2 and current_node_2.data == last_data: # in case this value is not unique in the list
            current_node_2 = current_node_2.next


def __and__(self, l):
    """
    Usage:
    l1 = LinkedList()
    l2 = LinkedList()
    l3 = l1 & l2 # performs intersection (ideally method intersection would never be invoked explicitly and should be renamed to _intersection)
    """
    assert isinstance(l, LinkedList)
    result = LinkedList()
    result.intersection(self, l)
    return result

Answer 3

Я внес несколько изменений / оптимизаций, которые применимы, если данные, хранящиеся в Node, можно хэшировать:

1. Добавлен метод __str__ для классов Node и LinkedList и удаленный метод display. Вы можете настроить их под свои нужды, но это гораздо более гибкий способ. Например, что вы хотели записать вывод связанного списка в файл на диске вместо терминала?
2. isempty просто сообщает, является ли текущий LinkedList пустым или нет, и ничего не печатает.
3. getsize сделан более эффективным.
4. intersection не требует сортированных связанных списков и очень эффективен. Однако он требует, чтобы данные, хранящиеся в узле, могут быть хэшируемыми. Например, вы не можете хранить list в узле, но можете хранить кортеж. Также будет представлена ​​вторая реализация intersection, которая не имеет этого ограничения, но будет работать медленнее. Я просто хотел представить другой вариант.