Given two sorted linked lists, where the result should be intersection without duplicities.

• Creating of new nodes is not allowed.
• The resulting list will be composed of the elements of the original lists.

Inputs are two lists separated by empty line:

L1 -> 2 3 3 4 4 4 5

L2 -> 3 4 5 6 7

Result -> 3 4 5

I have my solution below, but creating new node in IntersectionDestruct function.

Is there any simple way how to change IntersectionDestruct function with the logic of not creating any new node?

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    

CodePudding user response：

The only way how you can avoid Node creation for the result, is if you reuse nodes from a or b:

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

  while a and b:
    if a.data == b.data:
      if head is None:
        head = a # reusing a
        tail = head
      else:
        tail.next = a  # reusing a
        tail = tail.next

      a = a.next # here a is still pointing to the next node in a
      tail.next = None  # and here we completely detach current head from a
      b = b.next

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

Note, this implementation doesn't properly delete nodes from the original list a for simplicity, so that after LLIntersection is run both original list a and the LLIntersection result will share the same "tail" at some point.

CodePudding user response：

Your solution doesn't actually prevent duplicates, if you have a repeated number in both lists then advancing a and b together results in them matching again and the duplicate coming through in the result.

You should instead advance them both to a new number which would prevent any duplicates.

Then just reuse the original Nodes as well by assigning a to the list and clearing its next value so it doesn't leak into the existing list.

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

As this overwrites the next values on nodes from a, walking the list from a after this will give the same as before using the function up until the first item that intersected which had its next overwritten, then will be the intersecting values only after that.

So consider it corrupted, use the return value only.