使用python有两个带附加头结点的单链表,结点包含两个域:entry和next,若单链表中的元素值递增有序排列,请写算法,将两个单链表按顺序合并成一个链表。并运行一次
时间: 2023-05-30 21:03:57 浏览: 140
以下是使用Python实现的两个带附加头结点的单链表合并算法:
```python
class Node:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = Node()
def append(self, val):
new_node = Node(val)
cur = self.head
while cur.next:
cur = cur.next
cur.next = new_node
def __repr__(self):
nodes = []
cur = self.head.next
while cur:
nodes.append(str(cur.val))
cur = cur.next
return "->".join(nodes)
def merge_lists(l1, l2):
dummy = Node()
cur = dummy
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
if l1:
cur.next = l1
elif l2:
cur.next = l2
return dummy.next
# Example usage:
l1 = LinkedList()
l1.append(1)
l1.append(3)
l1.append(5)
l2 = LinkedList()
l2.append(2)
l2.append(4)
l2.append(6)
print(merge_lists(l1.head.next, l2.head.next))
# Output: 1->2->3->4->5->6
```
该算法的思路是,使用一个dummy结点来作为新链表的头结点,然后使用两个指针分别指向两个输入链表的头结点,比较它们的值大小,将较小的结点接到新链表的尾部,然后将指针向后移动。最后,将剩余的链表接到新链表的尾部即可。
阅读全文