NC293. 无环单链表插值
描述
有一个有序数组A和一个整数val，请你用A构造一个结点值有序的无环单链表，并对其插入一个结点值为val的结点，并且保证这个无环单链表依然有序。
示例1
输入:
[1,3,4,5,7],2
输出:
{1,2,3,4,5,7}
C++ 解法, 执行用时: 3ms, 内存消耗: 408KB, 提交时间: 2022-02-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/*
方法一：模拟
题意：根据数组构建链表，插入节点后仍使链表有序
需考虑待插入元素大于数组中所有元素的情况
*/
ListNode* insert(vector<int>& A, int val) {
bool flag = false; //标记是否已插入
ListNode* dummy = new ListNode(-1);
ListNode* p = dummy;
for(int i=0; i<A.size(); i++){
if(!flag && val < A[i]){
flag = true;
p->next = new ListNode(val);
p = p->next;
}
p->next = new ListNode(A[i]);
p = p->next;
}
if(!flag){ //待插入元素大于数组所有值时，在尾部插入
p->next = new ListNode(val);
p = p->next;
}
return dummy->next;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 432KB, 提交时间: 2022-02-23
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param val int整型
* @return ListNode类
*/
ListNode* insert(vector<int>& A, int val) {
// write code here
//构造链表
ListNode * head = NULL;
int size = A.size();
if(size == 0)
{
head = new ListNode(val);
return head;
}
head = new ListNode(A[0]);
ListNode * tmp = head;
for(int i=1;i<size;++i)
{
ListNode *p = new ListNode(A[i]);
tmp->next = p;
tmp = p;
}
tmp->next = NULL;
//插入
ListNode dummy(0);
dummy.next = head;
tmp = &dummy;
ListNode * p = new ListNode(val);
while(tmp->next != NULL)
{
if(val < tmp->next->val)
{
p->next = tmp->next;
tmp->next = p;
return dummy.next;
}
tmp = tmp->next;
}
tmp->next = p;
p->next = NULL;
return dummy.next;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 436KB, 提交时间: 2022-03-12
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param val int整型
* @return ListNode类
*/
ListNode* insert(vector<int>& A, int val) {
// write code here
ListNode* head = new ListNode(-1);
ListNode* tail = head;
for(int i=0;i<A.size();i++){
ListNode* p = new ListNode(A[i]);
tail->next = p;
tail = tail->next;
}
ListNode* p = head->next;
ListNode* q = head;
while(p && val>=p->val){
q = p;
p = p->next;
}
ListNode* node = new ListNode(val);
node->next = q->next;
q->next = node;
return head->next;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 440KB, 提交时间: 2022-06-13
class Solution {
public:
ListNode* insert(vector<int>& A, int val) {
bool flag = false;
ListNode* s = new ListNode(-1);
ListNode* p = s;
for (int i = 0; i < A.size(); i++) {
if (!flag && val < A[i]) {
flag = true;
p->next = new ListNode(val);
p = p->next;
}
p->next = new ListNode(A[i]);
p = p->next;
}
if (!flag) {
p->next = new ListNode(val);
p = p->next;
}
return s->next;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 444KB, 提交时间: 2022-02-10
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param val int整型
* @return ListNode类
*/
ListNode* insert(vector<int>& A, int val) {
// write code here
ListNode* head = new ListNode(-1);
ListNode* p = head;
if(val<=A[0]){
ListNode* data = new ListNode(val);
head->next = data;
head = head->next;
for(int i = 0;i < A.size();i++){
ListNode* data = new ListNode(A[i]);
head->next = data;
head = head->next;
}
}else if(val >= A[A.size()-1]){
for(int i = 0;i < A.size();i++){
ListNode* data = new ListNode(A[i]);
head->next = data;
head = head->next;
}
ListNode* data = new ListNode(val);
head->next = data;
head = head->next;
}
else{
ListNode* data = new ListNode(A[0]);
head->next = data;
head = head->next;
for(int i = 1;i < A.size();i++){
if(val>A[i-1] && val<=A[i]) {
data = new ListNode(val);
head->next = data;
head = head->next;
data = new ListNode(A[i]);
head->next = data;
head = head->next;
}else{
ListNode* data = new ListNode(A[i]);
head->next = data;
head = head->next;
}
}
}
return p->next;
}
};