头插法合并有序链表代码
时间: 2023-04-12 17:02:06 浏览: 68
以下是头插法合并有序链表的代码:
```
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && 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 ? l1 : l2;
return dummy->next;
}
```
希望能够帮到你!
相关问题
头插法创建单链表并实现合并
以下是Python实现头插法创建单链表并实现合并的代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def create_linked_list(arr):
head = ListNode()
for i in range(len(arr)):
node = ListNode(arr[i])
node.next = head.next
head.next = node
return head.next
def merge_linked_list(head1, head2):
dummy = ListNode()
cur = dummy
while head1 and head2:
if head1.val < head2.val:
cur.next = head1
head1 = head1.next
else:
cur.next = head2
head2 = head2.next
cur = cur.next
if head1:
cur.next = head1
if head2:
cur.next = head2
return dummy.next
```
其中,`create_linked_list`函数接受一个数组,返回一个以数组元素为节点值的头插法创建的单链表;`merge_linked_list`函数接受两个单链表的头结点,返回合并后的单链表的头结点。合并操作使用了归并排序的思想,将两个有序链表合并成一个有序链表。
将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间。表中允许有重复的数据。,使用头插法,写出代码实现
非常感谢您的问题!以下是代码实现:
```c
void mergeList(ListNode* list1, ListNode* list2) {
ListNode* p1 = list1->next;
ListNode* p2 = list2->next;
ListNode* temp;
list1->next = NULL;
while (p1 && p2) {
if (p1->val <= p2->val) {
temp = p1->next;
p1->next = list1->next;
list1->next = p1;
p1 = temp;
} else {
temp = p2->next;
p2->next = list1->next;
list1->next = p2;
p2 = temp;
}
}
if (p1) {
p2 = p1;
}
while (p2) {
temp = p2->next;
p2->next = list1->next;
list1->next = p2;
p2 = temp;
}
list2->next = NULL;
}
```
希望这个回答对您有所帮助!