设计把L1中与L2中数据相同的连续结点顺序完全
时间: 2023-06-12 15:07:25 浏览: 112
可以使用双指针的方法,首先将两个链表分别按照升序排列,然后分别从两个链表的头结点开始,比较当前结点的值大小,将值较小的结点插入到结果链表中,并将指针后移一位。如果两个结点的值相等,则将它们依次插入到结果链表中,直到有一个链表遍历完为止。最后,将未遍历完的链表中的剩余结点全部插入到结果链表的末尾即可。
具体实现可以参考下面的代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
# 将两个链表按升序排列
dummy = ListNode(-1)
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
cur.next = l1 if l1 else l2
return dummy.next
def mergeDuplicateNodes(head: ListNode) -> ListNode:
if not head or not head.next:
return head
# 将链表拆分成两个部分
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
l1, l2 = head, slow.next
slow.next = None
# 对两个链表进行排序合并
l1_sorted = mergeSort(l1)
l2_sorted = mergeSort(l2)
# 将两个链表中相同的连续结点顺序完全
dummy = ListNode(-1)
cur = dummy
while l1_sorted and l2_sorted:
if l1_sorted.val < l2_sorted.val:
cur.next = l1_sorted
l1_sorted = l1_sorted.next
elif l1_sorted.val > l2_sorted.val:
cur.next = l2_sorted
l2_sorted = l2_sorted.next
else:
cur1, cur2 = l1_sorted, l2_sorted
while cur1 and cur2 and cur1.val == cur2.val:
cur1 = cur1.next
cur2 = cur2.next
if not cur1 or (cur2 and cur1.val > cur2.val):
cur.next = l2_sorted
l2_sorted = cur2
else:
cur.next = l1_sorted
l1_sorted = cur1
cur = cur.next
cur.next = l1_sorted if l1_sorted else l2_sorted
return dummy.next
def mergeSort(head: ListNode) -> ListNode:
if not head or not head.next:
return head
# 将链表拆分成两个部分
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
l1, l2 = head, slow.next
slow.next = None
# 对两个链表进行归并排序
l1_sorted = mergeSort(l1)
l2_sorted = mergeSort(l2)
# 合并两个排序后的链表
return mergeTwoLists(l1_sorted, l2_sorted)
```
该算法的时间复杂度为 $O(n \log n)$,其中 $n$ 是链表的长度。
阅读全文