首页 > 试题广场 >

无环单链表插值

[编程题]无环单链表插值
  • 热度指数：1946 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

有一个有序数组A和一个整数val，请你用A构造一个结点值有序的无环单链表，并对其插入一个结点值为val的结点，并且保证这个无环单链表依然有序。

给定包含链表的所有元素的值（从头结点开始）的数组A，同时给定val，请构造出这个无环单链表，并返回插入该val值后的头结点。

数据范围：
0 < A.size() <= 1000
0 <= A中的元素值 <= 1000
0 < val <= 1000

例如当数组A为[1,3,4,5,7]，val为2时，插入val值后的链表变为{1,2,3,4,5,7}，如下图所示：

示例1

输入

[1,3,4,5,7],2

输出

{1,2,3,4,5,7}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
Java
爱睡觉的杨大爷头像 爱睡觉的杨大爷 
import java.util.*;
public class Solution {
    public ListNode insert (int[] A, int val) {
        // 数组有序，可以根据有序的数组创建单链表，在创建链表的过程中，拿val和每一个创建的节点进行比较
        //如果比节点小，就先创建val的节点，然后和链表相连,
        ListNode head=new ListNode(-1);
        ListNode cur=head;
        boolean flag=true;  //标志位，判断val是否已经插入,插入后变为false
        for(int i=0;i<A.length;i++){
            if(val<A[i]&&flag){
                ListNode node=new ListNode(val);
                cur.next=node;
                cur=cur.next;
                flag=false;
            }
            ListNode node=new ListNode(A[i]);
            cur.next=node;
            cur=cur.next;
        }
        if(flag){
            ListNode node=new ListNode(val);
            cur.next=node;
        }
        return head.next;
    }
}
时间复杂度为O(N),空间复杂度只用了有限几个变量，所以是O(1)。
发表于 2022-07-30 11:00:49 回复(1)
天明__头像 天明__ 
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <climits>
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(INT_MIN);
        ListNode* p = head;
        bool flag = false;
        for (int i = 0; i < A.size(); i++) {
            if (val <= A[i] && val > p->val) {
                ListNode* tmp = new ListNode(val);
                p->next = tmp;
                p = tmp;
                flag = true;
            }
            ListNode* temp = new ListNode(A[i]);
            p->next = temp;
            p = temp;
        }
        if (flag != true) {
            ListNode* tmp = new ListNode(val);
            p->next = tmp;
            p = tmp;
        }
        return head->next;
    }
};

发表于 2023-06-01 14:16:04 回复(0)
Python3
danspace头像 danspace 
import bisect
class Solution:
    def insert(self , A: List[int], val: int) -> ListNode:
        # write code here
        bisect.insort(A, val)
        dummy = ListNode(0)
        pre = dummy 
        for n in A:
            pre.next = ListNode(n)
            pre = pre.next 
        return dummy.next

发表于 2023-04-27 15:05:24 回复(0)
C
吾辈长歌头像 吾辈长歌 
struct ListNode* insert(int* A, int ALen, int val ) 
{
    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *p = dummy;
    struct ListNode *cur = dummy;

    int i = 0;

    while(i<ALen)
    {
        struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = A[i];
        p->next = node;
        p = p->next;
        i++;
    }

    int n = 0;

    while(n<ALen)
    {
        if(cur->next->val>val)
        {
            struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
            node->val = val;
            node->next = cur->next;
            cur->next = node;
            return dummy->next;
        }
        cur = cur->next;
        n++;
    }

    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    cur->next = node;

    return dummy->next;
}

发表于 2023-04-12 23:40:35 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main
import _"fmt"
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A int整型一维数组 
 * @param val int整型 
 * @return ListNode类
*/
func insert( A []int ,  val int ) *ListNode {
    node:=&ListNode{val,nil}
    head:=&ListNode{-1,nil}
    pre:=head
    flag:=false
    for _,x:=range A{
        cur:=&ListNode{x,nil}
        if x>val&&!flag{
            pre.Next=node
            node.Next=cur
            flag=true
        }else{
            pre.Next=cur
        }
        pre=cur
    }
    if !flag{
        pre.Next=node
    }
    return head.Next
}

发表于 2023-03-09 10:05:55 回复(0)
C
猪猪侠新新酱头像 猪猪侠新新酱 
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A int整型一维数组
 * @param ALen int A数组长度
 * @param val int整型
 * @return ListNode类
 */
struct ListNode* insert(int* A, int ALen, int val ) {
    // write code here
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* p1 = head;
    int i = 0;
    while (i < ALen) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->val = A[i];
        p1->next = node;
        p1 = p1->next;
        i++;
    }
    //struct ListNode *p2=head;
    struct ListNode* p3 = head;
    while (p3->next) {
        if (val < p3->next->val) {
            struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
            node->val = val;
            node->next = p3->next;
            p3->next = node;
            return head->next;
        }
        p3=p3->next;

    }
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    p3->next = node;
    return head->next;

}

发表于 2022-12-24 07:39:31 回复(0)
Javascript
一79头像 一79 
/**
function ListNode(x) {
  this.val = x;
  this.next = null;
}
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param A int整型一维数组
 * @param val int整型
 * @return ListNode类
 */
function insert(A, val) {
  A.push(val);
  A.sort(function (a, b) {
    return a - b;
  });
  let dummy = new ListNode();
  let temp = dummy;
  for (let i = 0; i < A.length; i++) {
    let newNode = new ListNode(A[i]);
    temp.next = newNode;
    temp = temp.next;
  }
  return dummy.next;
}
module.exports = {
  insert: insert,
};

发表于 2022-09-21 21:58:48 回复(0)
C++
zhengluoqi头像 zhengluoqi 
    ListNode* insert(vector<int>& A, int val) {
        bool flag = true;
        if (A.empty())return nullptr;
        ListNode* head = new ListNode(A[0]);
        int i = 1;
        if (val < A[0]) {
            head->val = val;
            i = 0;
            flag = false;
        }
        ListNode* L = head;
        while (i < A.size()) {
            if (flag && val < A[i]) {
                flag = false;
                L->next = new ListNode(val);
            } else {
                L->next = new ListNode(A[i]);
                i++;
            }
            L = L->next;
        }
        if (flag)L->next = new ListNode(val);
        return head;
    }

发表于 2022-07-27 00:30:56 回复(0)
Python 3
来牛客玩玩头像 来牛客玩玩 
class Solution:
    def insert(self , A: List[int], val: int) -> ListNode:
        # write code here
        A = sorted(A + [val])
        dummy = ListNode(0)
        head = ListNode(A[0])
        dummy.next = head
        for x in A[1:]:
            temp = ListNode(x)
            head.next = temp
            head = head.next
        return dummy.next

发表于 2022-07-26 15:32:36 回复(0)
Python 3
中正很头像 中正很 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param A int整型一维数组 
# @param val int整型 
# @return ListNode类
#
class Solution:
    def insert(self , A: List[int], val: int) -> ListNode:
        # write code here
        A.append(val)
        A.sort()
        pre = ListNode(-1)
        cur = pre
        for i in A:
            cur.next = ListNode(i)
            cur = cur.next
        return pre.next
            

发表于 2022-05-22 12:39:56 回复(0)
Java
镜花水月_头像 镜花水月_ 
import java.util.*;
public class Solution {
    public ListNode insert (int[] A, int val) {
        ListNode head = new ListNode(A[0]);
        //构建链表
        ListNode cur = head;
        for(int i = 1;i<A.length;i++){
            cur.next = new ListNode(A[i]);
            cur = cur.next;
        }
        //循环完成后cur指向当前链表最后一个节点
        
        //新建需要插入的节点
        ListNode temp = new ListNode(val);
        //如果要插入链表头部
        if(head.val>val){
            temp.next = head;
            return temp;
        //如果要插入链表尾部
        }else if(cur.val<val){
            cur.next = temp;
            return head;
        }
        //如果要插入中间
        cur = head;
        //寻找插入节点,这里要找到比val小的最后一个节点，所以要判断后面节点是否比val大
        while(cur.next.val<val){
            cur = cur.next;
        }
        //下面两个语句顺序不能颠倒
        temp.next = cur.next;
        cur.next = temp;
       return head; 
    }
}

发表于 2022-04-08 16:06:09 回复(0)
Java
世界杯2009头像 世界杯2009 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A int整型一维数组 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode insert(int[] A, int val) {
        // write code here
        ListNode head = new ListNode(0);
        ListNode cur = head;
        ListNode previous = head;
        boolean addFlag = false;
        for (int i = 0; i < A.length; i++) {
            int temp = A[i];
            if (temp < val) {
                cur.val = temp;
                cur.next = new ListNode(0);
                previous = cur;
                cur = cur.next;
            } else {
                if (!addFlag) {
                    cur.val = val;
                    cur.next = new ListNode(0);
                    previous = cur;
                    cur = cur.next;
                }
                cur.val = temp;
                cur.next = new ListNode(0);
                previous = cur;
                cur = cur.next;
                addFlag = true;
            }
        }

        if (!addFlag) {
            // 最后一个加入val
            cur.val = val;
            cur.next = new ListNode(0);
            previous = cur;
            cur = cur.next;
        }
        previous.next = null;

        return head;
    }
}

发表于 2022-03-16 22:42:23 回复(0)
提交观点

问题信息

链表
上传者：牛客301499号
难度：
12条回答 1256浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号