Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
题意就是合并两个排序链表。
我的算法思路：维护其中一个链表，另一个链表从头往后不断缩减，并将每次出队的节点插入到第一个链表中。因此时间复杂度为O(n),空间复杂度为O(1)。
然而LeetCode给的链表接口是head->next，所以我的代码只能合并从第二个节点开始的剩余部分。
传入参数为头节点(head)的方案：
#include <iostream>
struct ListNode {
int val;
ListNode *next;
//ListNode(int x) : val(x), next(NULL) {}
};
ListNode* Create_LinkList_1(int Length) {
ListNode*L1, *rear, *memory;
L1 = new ListNode;
rear = L1;
for(int i = 1; i <= Length; i++) {
memory = new ListNode;
std::cout << "L1:";
std::cin >> memory->val;
rear->next = memory;
rear = memory;
}
rear->next = nullptr;
return L1;
}
ListNode* Create_LinkList_2(int Length) {
ListNode*L2, *rear, *memory;
L2 = new ListNode;
rear = L2;
for(int i = 1; i <= Length; i++) {
memory = new ListNode;
std::cout << "L2:";
std::cin >> memory->val;
rear->next = memory;
rear = memory;
}
rear->next = nullptr;
return L2;
}
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!(l1 && l2))
return nullptr;
else if(l1 && !l2)
return l1;
else if(!l1 && l2)
return l2;
else {
// 2->4->6 1->3->5
ListNode*head = l1;
ListNode*p1 = l1->next;
ListNode*p2 = l2->next;
ListNode*q1;
while(p1 && p2) {
if(p1->val >= p2->val) {
ListNode*node = p2;
p2 = p2->next;
node->next = p1;
if(p1 == head->next)
head->next = node;
else
q1->next = node;
p1 = node;
p1 = p1->next;
}
q1 = p1;
p1 = p1->next;
}
if (p2)
q1->next = p2;
return head;
}
}
};
int main()
{
Solution solve;
ListNode* L1, *L2;
L1 = Create_LinkList_1(3);
L2 = Create_LinkList_2(3);
ListNode*head = solve.mergeTwoLists(L1, L2)->next;
while(head) {
std::cout << head->val << ‘ ‘;
head = head->next;
}
return 0;
}
传入参数是head->next的方案：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!(l1 && l2))
return NULL;
else if(l1 && !l2)
return l1;
else if(!l1 && l2)
return l2;
else {
ListNode*head = l1;
ListNode*q1 = l1;
while(l1 && l2) {
if(l1->val >= l2->val) {
ListNode*node = l2;
l2 = l2->next;
if (head == l1) {
node->next = l1->next;
l1->next = node;
} else {
node->next = l1;
q1->next = node;
l1 = node;
}
l1 = l1->next;
}
q1 = l1;
l1 = l1->next;
}
if (l2)
q1->next = l2;
return head;
}
}
};
但没有过：
目前我猜测是因为LeedCode的特殊数据，链表l1只有1个节点(还有一个头节点，但传入的是l1=head->next)，且不为空，但没有给成员val赋值，这样的话，我的算法就会被卡住了。