python - Alternate linked list merge - Stack Overflow

admin管理员组

文章数量:1122846

I wanted to merge 2 linked list’s elements alternatively. I counted the length of these 2 linked lists manually, then created a dummy-headed node to use for the merge. I am getting the errors "AttributeError: 'NoneType' object has no attribute 'elem'" and I think my approach is quite inefficient.

I have a few restrictions, like I cannot use any built-in functions or negative indexing.

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

def createList(arr):
  head = Node(arr[0])
  tail = head
  for i in range(1,len(arr)):
    newNode = Node(arr[i])
    tail.next = newNode
    tail = newNode
  return head

def printLinkedList(head):
  temp = head
  while temp != None:
    if temp.next != None:
      print(temp.elem, end = '-->')
    else:
      print(temp.elem)
    temp = temp.next
  print()


def alternate_merge(head1, head2):
  counter1 = 0
  counter2 = 0

  temp1 = head1
  temp2 = head2

  while temp1!=None:
    counter1+=1
    temp1 = temp1.next
  while temp2!=None:
    counter2+=1
    temp2 = temp2.next
  
  if counter1<counter2:
    counter = counter1
  else:
    counter = counter2

  temp1 = head1
  temp2 = head2

  head = Node(None)
  h_temp = head 
  h_temp.elem = temp1.elem
  temp1 = temp1.next

  for i in range(counter):
    h_temp.next = Node(temp2.elem)
    temp2 = temp2.next
    h_temp = h_temp.next
    h_temp.next = Node(temp1.elem)
    temp1 = temp1.next
  return h_temp 



print('==============Test Case 1=============')
head1 = createList(np.array([1,2,6,8,11]))
head2 = createList(np.array([5,7,3,9,4]))

print("Linked List 1:")
printLinkedList(head1)
print("Linked List 2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("Merged Linked List:")
printLinkedList(head)    #This should print    1 --> 5 --> 2 --> 7 --> 6 --> 3 --> 8 --> 9 --> 11 --> 4


print('==============Test Case 2=============')
head1 = createList(np.array([5, 3, 2, -4]))
head2 = createList(np.array([-4, -6, 1]))

print("Linked List 1:")
printLinkedList(head1)
print("Linked List 2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("Merged Linked List:")
printLinkedList(head)    #This should print    5 → -4 -> 3 → -6 -> 2 -> 1 -> -4


print('==============Test Case 3=============')
head1 = createList(np.array([4, 2, -2, -4]))
head2 = createList(np.array([8, 6, 5, -3]))

print("Linked List 1:")
printLinkedList(head1)
print("Linked List 2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("Merged Linked List:")
printLinkedList(head)    #This should print   4-> 8 → 2-> 6 → -2 → 5 → -4 -> -3

I wanted to merge 2 linked list’s elements alternatively. I counted the length of these 2 linked lists manually, then created a dummy-headed node to use for the merge. I am getting the errors "AttributeError: 'NoneType' object has no attribute 'elem'" and I think my approach is quite inefficient.

I have a few restrictions, like I cannot use any built-in functions or negative indexing.

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

def createList(arr):
  head = Node(arr[0])
  tail = head
  for i in range(1,len(arr)):
    newNode = Node(arr[i])
    tail.next = newNode
    tail = newNode
  return head

def printLinkedList(head):
  temp = head
  while temp != None:
    if temp.next != None:
      print(temp.elem, end = '-->')
    else:
      print(temp.elem)
    temp = temp.next
  print()


def alternate_merge(head1, head2):
  counter1 = 0
  counter2 = 0

  temp1 = head1
  temp2 = head2

  while temp1!=None:
    counter1+=1
    temp1 = temp1.next
  while temp2!=None:
    counter2+=1
    temp2 = temp2.next
  
  if counter1<counter2:
    counter = counter1
  else:
    counter = counter2

  temp1 = head1
  temp2 = head2

  head = Node(None)
  h_temp = head 
  h_temp.elem = temp1.elem
  temp1 = temp1.next

  for i in range(counter):
    h_temp.next = Node(temp2.elem)
    temp2 = temp2.next
    h_temp = h_temp.next
    h_temp.next = Node(temp1.elem)
    temp1 = temp1.next
  return h_temp 



print('==============Test Case 1=============')
head1 = createList(np.array([1,2,6,8,11]))
head2 = createList(np.array([5,7,3,9,4]))

print("Linked List 1:")
printLinkedList(head1)
print("Linked List 2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("Merged Linked List:")
printLinkedList(head)    #This should print    1 --> 5 --> 2 --> 7 --> 6 --> 3 --> 8 --> 9 --> 11 --> 4


print('==============Test Case 2=============')
head1 = createList(np.array([5, 3, 2, -4]))
head2 = createList(np.array([-4, -6, 1]))

print("Linked List 1:")
printLinkedList(head1)
print("Linked List 2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("Merged Linked List:")
printLinkedList(head)    #This should print    5 → -4 -> 3 → -6 -> 2 -> 1 -> -4


print('==============Test Case 3=============')
head1 = createList(np.array([4, 2, -2, -4]))
head2 = createList(np.array([8, 6, 5, -3]))

print("Linked List 1:")
printLinkedList(head1)
print("Linked List 2:")
printLinkedList(head2)

head = alternate_merge(head1, head2)
print("Merged Linked List:")
printLinkedList(head)    #This should print   4-> 8 → 2-> 6 → -2 → 5 → -4 -> -3

• python
• data-structures
• merge
• singly-linked-list

Share Improve this question Follow asked Nov 21, 2024 at 23:53 RINRIN 1122 bronze badges 3

• Why count before merging? – greybeard Commented Nov 22, 2024 at 1:53
• What to do if lengths differ by more than 1? – greybeard Commented Nov 22, 2024 at 8:20
• What do you mean by "I cannot use any built-in functions"? It seems incongruous that you can't use built-in functions but you can install and utilise numpy – SIGHUP Commented Nov 22, 2024 at 9:24

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 0

I think this line of code is the problem, just before the main loop in alternate_merge():

temp1 = temp1.next

You're advancing temp1 to the next item in the list, so there are only four items left in head1, but the loop still tries to run for five iterations, so it runs off the end of the list.

Why are you advancing temp1 to the next item before the loop even starts?

Some issues in your attempt:

• As you have already added a node from the first list before the loop, your loop will iterate one step too far and try to access the attributes of a node that does not exist. Another way to look at this problem is this: as your loop intends to append two nodes per iteration, and one node is appended before the loop, your program is designed to create a merged list with an odd number of nodes, yet it is clear that sometimes this number has to be even.

  A related problem is that your code will also fail when the first list is empty.

• you only advance h_temp once in your loop body, while that loop body appends two nodes.

• You return the wrong node. h_temp has advanced potentially several times during the loop, so if you return that node, you'll have skipped several other nodes that came before it, not just the dummy node.

• Not sure if it is a problem, but if your lists have completely different sizes, the resulting list will not have all of the values present in the input lists; you'll omit some nodes from the longer input list. It seems better to just copy those nodes into the merged list as well.

Taking a step back, you should not have to count the nodes in the lists. Instead make your loop condition such that it tests whether there are still nodes to merge, so that the loop body will not access a node that doesn't exist.

I would further suggest to avoid some code repetition and only add one node per loop iteration, while swapping the roles of the two input lists, so that the next iteration will take a node from the "other" list.

Here is how it could work:

def alternate_merge(head1, head2):
    tail = dummy = Node(None)  # Use a dummy node
    if not head1:  # Deal with boundary case
        head1, head2 = head2, head1  # Swap roles of the lists
    while head1:  # Iterate as long as there is a node to merge
        tail.next = Node(head1.elem)  # Add a node
        tail = tail.next
        head1 = head1.next # Advance
        if head2: # Should we still alternate?
            head1, head2 = head2, head1  # Swap roles of the lists
    return dummy.next  # What follows the dummy node is the head node

本文标签： pythonAlternate linked list mergeStack Overflow