将两个从小到大排列的链表合并为一个新链表(仍然有序排列),若遇到相同的元素,则在合并时去掉重复元素。输出合并前的两个链表,输出合并后的链表,检查合并是否成功。
时间: 2023-06-05 19:47:08 浏览: 146
好的,以下是中文回复:
题目要求我们将两个已经从小到大排列的链表合并为一个新链表,并且在合并时去掉重复元素。我们可以先遍历两个链表,将它们的元素按照从小到大的顺序依次放入一个新的链表中,如果遇到相同的元素,则只保留一个。最后输出合并前的两个链表和合并后的链表,检查合并是否成功。
以下是示例代码:
```python
class ListNode:
def __init__(self, val=, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 创建一个新链表
dummy = ListNode()
cur = dummy
# 遍历两个链表
while l1 and l2:
if l1.val < l2.val:
cur.next = ListNode(l1.val)
l1 = l1.next
elif l1.val > l2.val:
cur.next = ListNode(l2.val)
l2 = l2.next
else:
cur.next = ListNode(l1.val)
l1 = l1.next
l2 = l2.next
cur = cur.next
# 将剩余的元素加入新链表
if l1:
cur.next = l1
if l2:
cur.next = l2
# 去掉重复元素
cur = dummy.next
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
# 返回新链表
return dummy.next
# 测试代码
if __name__ == '__main__':
l1 = ListNode(1, ListNode(2, ListNode(3)))
l2 = ListNode(2, ListNode(3, ListNode(4)))
s = Solution()
merged = s.mergeTwoLists(l1, l2)
print("合并前的两个链表:")
print("l1: ", end="")
while l1:
print(l1.val, end=" ")
l1 = l1.next
print("\nl2: ", end="")
while l2:
print(l2.val, end=" ")
l2 = l2.next
print("\n合并后的链表:")
while merged:
print(merged.val, end=" ")
merged = merged.next
```
输出结果为:
```
合并前的两个链表:
l1: 1 2 3
l2: 2 3 4
合并后的链表:
1 2 3 4
```
可以看到,合并前的两个链表分别为 1->2->3 和 2->3->4,合并后的链表为 1->2->3->4,去掉了重复的元素 2 和 3,合并成功。
阅读全文