删除线性链表倒数第i个结点

可以使用双指针法来解决这个问题。首先，让一个指针从链表的头部开始移动 i 个位置，然后让另一个指针从链表的头部开始移动，直到第一个指针到达链表的末尾。此时，第二个指针所指向的结点就是倒数第 i 个结点。然后，我们可以将该结点从链表中删除即可。

以下是示例代码：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *p = head, *q = head;
    for (int i = 0; i < n; i++) {
        p = p->next;
    }
    if (!p) {
        return head->next;
    }
    while (p->next) {
        p = p->next;
        q = q->next;
    }
    q->next = q->next->next;
    return head;
}

这段代码实现了删除链表倒数第 n 个结点的功能。如果链表长度小于 n，直接返回 head->next 即可。

相关问题

删除线性链表倒数第n个结点

可以使用双指针法来解决这个问题。首先，让一个指针指向链表的头部，另一个指针指向第n个结点。然后，让两个指针同时向后移动，直到第二个指针到达链表的末尾。此时，第一个指针所指向的结点就是要删除的结点。

具体实现可以参考以下代码：

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode *p1 = head, *p2 = head;
    for (int i = 0; i < n; i++) {
        p2 = p2->next;
    }
    if (!p2) {
        return head->next;
    }
    while (p2->next) {
        p1 = p1->next;
        p2 = p2->next;
    }
    p1->next = p1->next->next;
    return head;
}

这段代码实现了删除链表倒数第n个结点的功能。如果链表长度小于n，则直接返回头结点的下一个结点。否则，使用双指针法找到要删除的结点，并将其从链表中删除。

实现线性表的链式存储定义，完成单链表的创建（头插法、尾插法）、插入、删除、查找等常用操作，将线性链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，以此类推。

线性表的链式存储定义：

typedef struct node {
    int data;
    struct node *next;
} Node, *LinkedList;

其中，`data` 表示结点中存储的数据，`next` 表示指向下一个结点的指针，`LinkedList` 表示头结点的指针。

单链表的创建：

头插法：

LinkedList createListHead(int n) {
    LinkedList head = (LinkedList) malloc(sizeof(Node));
    head->next = NULL;
    for (int i = 0; i < n; i++) {
        LinkedList newNode = (LinkedList) malloc(sizeof(Node));
        printf("请输入第%d个结点的值：", i + 1);
        scanf("%d", &(newNode->data));
        newNode->next = head->next;
        head->next = newNode;
    }
    return head;
}

尾插法：

LinkedList createListTail(int n) {
    LinkedList head = (LinkedList) malloc(sizeof(Node));
    head->next = NULL;
    LinkedList tail = head;
    for (int i = 0; i < n; i++) {
        LinkedList newNode = (LinkedList) malloc(sizeof(Node));
        printf("请输入第%d个结点的值：", i + 1);
        scanf("%d", &(newNode->data));
        newNode->next = NULL;
        tail->next = newNode;
        tail = newNode;
    }
    return head;
}

插入操作：

在第 i 个结点后插入一个值为 x 的结点：

bool insert(LinkedList L, int i, int x) {
    LinkedList p = L;
    for (int j = 0; j < i - 1; j++) {
        p = p->next;
        if (p == NULL) {
            printf("插入位置不合法\n");
            return false;
        }
    }
    LinkedList newNode = (LinkedList) malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = p->next;
    p->next = newNode;
    return true;
}

删除操作：

删除第 i 个结点：

bool delete(LinkedList L, int i) {
    LinkedList p = L;
    for (int j = 0; j < i - 1; j++) {
        p = p->next;
        if (p == NULL) {
            printf("删除位置不合法\n");
            return false;
        }
    }
    LinkedList q = p->next;
    if (q == NULL) {
        printf("删除位置不合法\n");
        return false;
    }
    p->next = q->next;
    free(q);
    return true;
}

查找操作：

查找值为 x 的结点：

LinkedList find(LinkedList L, int x) {
    LinkedList p = L->next;
    while (p != NULL && p->data != x) {
        p = p->next;
    }
    return p;
}

逆置操作：

LinkedList reverse(LinkedList L) {
    LinkedList newHead = L;
    LinkedList p = L->next;
    L->next = NULL;
    while (p != NULL) {
        LinkedList q = p->next;
        p->next = newHead->next;
        newHead->next = p;
        p = q;
    }
    return newHead;
}