交替链表合并

问题描述 投票:0回答:1

我想交替合并两个链表的元素。我手动计算了这两个链表的长度,然后创建了一个虚拟头节点用于合并。我收到错误“AttributeError:'NoneType'对象没有属性'elem'”,我认为我的方法效率很低。

我有一些限制,比如我不能使用任何内置函数或负索引。

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
1个回答
0
投票

我认为这段代码是问题所在,就在

alternate_merge()
中的主循环之前:

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

因为您正在分配

temp1 = temp1.next
,所以
temp1
指针从列表中的第二项开始,因此它超出了一步,然后循环从
head1
列表的末尾运行。

© www.soinside.com 2019 - 2024. All rights reserved.