链表删除位置N的节点

Question

编辑：找出问题所在。另外，如果您通过谷歌或其他搜索引擎发现了这个问题，这里就是我出错的地方以及如何修复它。

我的deleteNode()方法以正确的温度正确地在列表中移动，并保持头部不变。我出错的地方在于我作为该方法的结果返回的内容。我返回了 temp 或 newNode，这是不正确的，因为它会遍历列表直到找到定义的位置。一旦找到定义的位置，它将重新分配 ->next 指针以指向下一个 ->next> 位置。指针是正确的，但我再次返回了错误的东西。因为我们已经使用 temp/NewNode 移动了列表，所以我们丢失了标题，并且我们返回了我们找到的位置以及列表中下一个位置中仍然存在的内容。

我们如何解决这个问题是返回头部（这是传递到方法中的内容）。之所以有效，是因为我们必须了解 LinkedList 的工作原理。每个节点的指针都指向下一个节点。前任。我们有一个链表 |A|| - |B|| - |C|| - |D|| - |E|| - |F||

如果我们想删除节点 C，我们使用临时指针移动到节点 B，然后将 B->next 分配给 temp->next->next，从而跳过 C 节点并分配 D 节点。

注意：（据我所知，这实际上并没有释放 C 节点的内存，因此这不是最佳实践，因为这样可能会导致内存泄漏）您应该在 C 节点上使用 free() 方法。

这是我最终使用的代码，

struct node* DeleteNode(struct node* head, int pos) {

     struct node* temp = head;
     int length = LinkedListLength(temp);
     int i;

    if(pos <= 0 || pos > length){
        printf("ERROR: Node does not exist!\n");
    }else{
        if(pos == 1){
            head = head->next; //move from head (1st node) to second node
        }else{
            for(i = 1; i < pos-1; ++i){ //move through list
                    temp = temp->next;
            }
            temp->next = temp->next->next;
        }
    }
    return head;
}

希望有助于理解我是如何修复它的。

/////////////////////////////////////////////////////////// /////////////////////////////////////////////////
/////////////////////////////////////////////////////////// /////////////////////////////////////////////////
原帖
/////////////////////////////////////////////////////////// /////////////////////////////////////////////////
/////////////////////////////////////////////////////////// ////////////////////////////////////////////////

编辑： 注意：这是一项家庭作业，我花了几天（估计 4 小时）对其进行编程，我只是卡在这一部分上。您可以在下面查看我的尝试

我已经能够从开始/结束处插入和删除，但是我似乎无法让链接列表中位置 N 的删除节点正常工作。

我的伪代码如下所示：

1. LinkedList: 1,3,5,7,9,23
2. Grab LinkedList
3. 创建新的结构节点 A = head
4. 通过链表移动直到 位置
5. 将节点分配给节点->下一个
6. 返回链接列表

示例输入

Node structure 
int data;
struct node* next;

int values[] = {1,3,5,7,9,23};
struct node* llist = CreateList(values,6);

llist = DeleteNode(llist, 1);
llist = DeleteNode(llist, 5);
llist = DeleteNode(llist, 3);

一旦代码运行，应该将 llist 保留为值 3、5、9 但是，它用 0 替换第一个节点

实际代码：

struct node* DeleteNode(struct node* head, int pos) {

struct node* temp = head;
struct node* newNode = head;
int length;
int i;

printf("DeleteNode: position = %d \nBefore: ", pos);
PrintList(temp);

if(pos <= 0){ //node does NOT exist
    printf("ERROR: Node does not exist!\n");
}else{ //node DOES exist
    length = LinkedListLength(temp);

    if(length < pos){ //if length < position Node does not exist
        printf("ERROR: Node does not exist!\n");
    }else{
        if(pos == 0){
            newNode = temp->next;
        }else if(pos == 1){
            newNode = temp->next;
        }else{
            for(i = 1; i < pos; i++){
                printf("i = %d\n", i);
                temp = temp->next;
                newNode->next;
            }
            if(temp->next == NULL){
                newNode = NULL;
            }else{
                newNode = temp->next;
            }
        }
    printf("After: ");
    PrintList(newNode);
    printf("\n");
    }
}
return newNode;
}

编辑#2：代码拼写错误

感谢您提前提供的任何帮助。根据我的结论，我的问题是我没有正确地浏览列表，但我不确定为什么我没有。

Answer 1

有该行

newNode->next;

在您的代码中，您的 for 循环中 。该操作没有任何作用。

你还有

newNode-> = NULL;

which 不是有效的C，我不知道你是如何编译它的。

但实际上，不要使用该循环。链表是最基本的递归数据结构之一。因此，几乎所有操作它们的算法都是最优雅的递归解决方案。

typedef struct node node_t;

node_t* delete_at_index(node_t* head, unsigned i)
{
    node_t* next;

    if(head == NULL)
        return head;

    next = head->next;

    return i == 0
             ? (free(head), next)                                 /* If i == 0, the first element needs to die. Do it. */
             : (head->next = delete_at_index(next, i - 1), head); /* If it isn't the first element, we recursively check the rest. */
}

Answer 2

从单链表中删除给定节点 n 可以归结为以下操作：

• 将指向 n 的指针设置为指向 n-> ;下一步。

您可以将其分解为两个操作：

• 查找指向 n 的指针；
• 将该指针设置为n->next。

出现问题的原因是，指向 n 的指针可能是列表中前一个节点的 p->next 字段，或者是 head code> 指针（如果 n 是列表中的第一个节点）。

您的代码似乎并不完整 - 它从未将任何节点的 ->next 字段设置为任何内容，因此很难说到底出了什么问题。

Answer 3

// Remove list's node located at specified position.
// Arguments:
//  head -- list's head
//  pos -- index of a node to be removed (1-based!!!)

struct node* DeleteNode(struct node* head, int pos) 
{

    struct node* node;
    struct node* prev;
    int length;
    int i;

    printf("DeleteNode: position = %d \nBefore: ", pos);
    PrintList(head);

    // Check position's lower bound. Should be >= 1
    if(pos <= 0) { //node does NOT exist
        printf("ERROR: Node does not exist!\n");
        return head;
    }

    // Seek to the specified node, and keep track of previous node.
    // We need previous node to remove specified node from the list.

    for(i=1, prev = 0, node = head; i < pos && node != 0; i++) {
        prev = node;
        node = node->next;
    }

    // Out of range
    if(0 == node) {
        printf("ERROR: Index out of bounds!\n");
        return head;
    }

    // @node points to a list's node located at index pos 
    // @prev points to a previous node.

    // Remove current node from the list.
    if(0 == prev) {
        head = node->next;
    }
    else {
        prev->next = node->next;
    }
    free(node);

    return head;   
}

Answer 4

您的DeleteNode不会删除节点，它会从列表的前面删除pos节点。因此，您尝试从仅包含 6 个项目的列表中删除 9 个项目，这当然会导致空列表 (NULL)。此外，您的代码过于复杂，并且包含以前尝试的残余内容。请不要对自己或我们这样做；提供简单干净的代码，它会更容易理解和修复。

Answer 5

发现你的 for 循环没有达到你想要的位置。
最好使用等号来表示它起作用的约束。
例如

for (i=1;i<=position-1;i++)
{

}