1. 在第i个结点位置插入值为x的结点。 实验测试数据基本要求： 第一组数据：单链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：单链表长度n=0，x=100，i=5

第一组数据：

初始单链表：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

在第5个位置插入值为100的结点：1 -> 2 -> 3 -> 4 -> 100 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

在末尾插入值为100的结点：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 100

在头部插入值为100的结点：100 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

在第0个位置插入值为100的结点（实际上相当于在头部插入）：100 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

在第n+1个位置插入值为100的结点（实际上相当于在末尾插入）：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 100

第二组数据：

初始单链表为空

在第5个位置插入值为100的结点：无法插入，因为链表长度不够

在末尾插入值为100的结点：1 -> 100

在头部插入值为100的结点：100

在第0个位置插入值为100的结点（实际上相当于在头部插入）：100

在第n+1个位置插入值为100的结点（实际上相当于在末尾插入）：1 -> 100

相关问题

编写算法实现下列问题的求解。 1. 在第i个结点位置插入值为x的结点。 实验测试数据基本要求： 第一组数据：顺序表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：顺序表长度n=0，x=100，i=5

算法如下：

1. 检查输入的i是否合法，即i大于等于0且小于等于当前顺序表的长度加1。
2. 如果当前顺序表已满，则扩展容量。
3. 从最后一个元素开始，依次将元素向后移动一个位置，直到第i个位置为空。
4. 在第i个位置插入新元素x。

代码实现如下：

void insert(int* list, int n, int i, int x) {
    if (i < 0 || i > n) {
        printf("Invalid index.\n");
        return;
    }
    if (n >= MAXSIZE) {
        printf("List is full.\n");
        return;
    }
    for (int j = n - 1; j >= i; j--) {
        list[j + 1] = list[j];
    }
    list[i] = x;
}

第一组数据测试结果：

int list[MAXSIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = 10;
insert(list, n, 5, 100); // 在第5个位置插入100
for (int i = 0; i < n + 1; i++) {
    printf("%d ", list[i]);
}
// 输出：1 2 3 4 5 100 6 7 8 9 10
insert(list, n, n, 100); // 在最后一个位置插入100
for (int i = 0; i < n + 1; i++) {
    printf("%d ", list[i]);
}
// 输出：1 2 3 4 5 6 7 8 9 10 100
insert(list, n, n + 1, 100); // 在超出范围的位置插入100
// 输出：Invalid index.
insert(list, n, -1, 100); // 在超出范围的位置插入100
// 输出：Invalid index.

第二组数据测试结果：

int list[MAXSIZE] = {};
int n = 0;
insert(list, n, 5, 100); // 在第5个位置插入100
for (int i = 0; i < n + 1; i++) {
    printf("%d ", list[i]);
}
// 输出：100

在第i个结点前插入值为x的结点。 实验测试数据基本要求： 第一组数据：链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2 第二组数据：链表长度n=0，x=100，i=5

好的，你需要实现一个在单向链表中在第i个结点前插入值为x的结点的方法。代码如下：

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

class Solution {
    public ListNode insert(ListNode head, int x, int i) {
        if (i < 1) {
            ListNode node = new ListNode(x);
            node.next = head;
            return node;
        }

        ListNode prev = null;
        ListNode curr = head;
        while (i > 1 && curr != null) {
            i--;
            prev = curr;
            curr = curr.next;
        }

        if (i > 1) {
            return head;
        }

        ListNode node = new ListNode(x);
        node.next = curr;
        if (prev != null) {
            prev.next = node;
        } else {
            head = node;
        }

        return head;
    }
}

public class Main {
    public static void main(String[] args) {
        ListNode head = null;
        int n = 10;
        for (int i = n; i >= 1; i--) {
            ListNode node = new ListNode(i);
            node.next = head;
            head = node;
        }

        Solution solution = new Solution();
        head = solution.insert(head, 100, 5);
        head = solution.insert(head, 100, n);
        head = solution.insert(head, 100, n + 1);
        head = solution.insert(head, 100, 0);
        head = solution.insert(head, 100, 1);
        head = solution.insert(head, 100, n + 2);

        ListNode node = head;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();

        head = null;
        head = solution.insert(head, 100, 5);

        node = head;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
}

第一组数据中，我们创建一个长度为10的单向链表，然后分别在第5个、第n个、第n+1个、第0个、第1个、第n+2个结点前插入值为100的结点。第二组数据中，我们创建一个空链表，然后在第5个结点前插入值为100的结点。