删除单链表首尾的第n个节点

Question

我刚开始学习链表。

我可以想出一种方法来分别从开头和结尾删除第 n 个节点，但我无法处理同时执行这两个节点所需的检查。

从头到尾都删除第n个节点

输入：

1->2->3->4->5->6->7->8->9->10->NULL
N =4

输出：

1->2->3->5->6->8->9->10->NULL

从开头删除：

void deletePosition(struct Node** head, int n){
struct Node* temp = *head;
struct Node* previous;

int size=0;

while(node!=NULL){
    node = node->next;
    size++;
}

if(n < 1 || n > size){
    return;
}

if(n == 1){
    *head = (*head)->next;
    free(temp);
    return;
}

while (--n) 
{
    previous = temp; 
    temp = temp->next; 
}
previous->next = temp->next;

free(temp);

}

从末尾删除：

    Node* deleteNode(Node* head, int key)
{
    Node* temp;
    Node* first = head;
    Node* second = head;
    for (int i = 0; i < key; i++) {
        if (second->next == NULL) {
            if (i == key - 1) {
                temp = head;
                head = head->next;
                free(temp);
            }
            return head;
        }
        second = second->next;
    }
 
    while (second->next != NULL) {
        first = first->next;
        second = second->next;
    }
 
    temp = first->next;
    first->next = first->next->next;
    free(temp);
    return head;
}

通用算法或伪代码将不胜感激。

Answer 1

假设你在节点 3。

helper = this -> next -> next;
delete this -> next;
this -> next = helper;

所以基本上您需要在删除之前到达您要删除的节点之后的节点，否则将无法访问它。

检查是否有任何节点：

if(root == NULL)
{
 /// there are no nodes
}

如果有节点：

traverse = root;
int count = 0;
while(traverse != NULL)
{
   ++count;
   if(count == n)
   { /* you are at the nth node */ }
   traverse = traverse -> next;
}

请注意，如果您删除节点 n 而您仍在节点 (n-1) 处，则您只需执行单独的“索引转换”，也就是说，删除另一个节点。所以如果你想删除之前是第 p 个节点的另一个节点，那么只需在 if 语句中执行


///the deletion
++count;

实际上，当您到达第 p 个节点时，您将得到 count == p，直到任何删除。

Answer 2

对于你我这样的初学者来说，这个任务并不简单。

尽管如此，我们初学者还是应该互相帮助。

对于初学者，C++ 中的索引从 0 开始。

其次你应该检查从尾部开始的指针是否等于从头开始的指针。或者一个指针是否是另一个指针指向的节点的下一个数据成员的指针。

例如，如果两个指针彼此相等，则只需删除列表中的一个节点。

我不会写伪代码。这对我来说太复杂了。所以你来了

#include <iostream>
#include <iomanip>
#include <functional>

struct ListNode
{
    int val;
    ListNode *next;
};


void clear( ListNode * &head )
{
    while (head)
    {
        delete std::exchange( head, head->next );
    }
}

void create( ListNode *&head, const int a[], size_t n )
{
    clear( head );

    for (ListNode **current = &head; n--; current = &( *current )->next)
    {
        *current = new ListNode{ *a++, nullptr };
    }
}

std::ostream &display( const ListNode *head, std::ostream &os = std::cout )
{
    for (const ListNode *current = head; current != nullptr; current = current->next)
    {
        os << current->val << " -> ";
    }

    return os << "null";
}

void swap( ListNode *&current )
{
    if (current && current->next)
    {
        ListNode *&next = current->next;
        std::swap( current, next );
        std::swap( current->next, next->next );
        swap( next );
    }
}

bool remove_two_sides_n( ListNode * &head, size_t n )
{
    ListNode **left = &head;

    while (*left && n--) left = &( *left )->next;

    if (*left == nullptr) return false;

    ListNode **right = &head;
    ListNode *last = *left;

    while (last->next)
    {
        right = &( *right )->next;
        last = last->next;
    }


    if (( *right )->next == *left) std::swap( left, right );

    if ( right != left )
    {
        ListNode *tmp = *right;
        *right = ( *right )->next;
        delete tmp;
    }

    ListNode *tmp = *left;
    *left = ( *left )->next;
    delete tmp;

    return true;
}

int main()
{
    const size_t N = 9;

    for (size_t i = 0; i < N + 1; i++)
    {
        ListNode *head = nullptr;
        const int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

        create( head, a, sizeof( a ) / sizeof( *a ) );

        std::cout << std::setw( 2 ) << i << ": ";
        display( head ) << '\n';

        remove_two_sides_n( head, i );

        std::cout << std::setw( 2 ) << i << ": ";
        display( head ) << '\n';

        clear( head );

        std::cout << '\n';
    }
}

程序输出为

 0: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 0: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

 1: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 1: 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9 -> null

 2: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 2: 1 -> 2 -> 4 -> 5 -> 6 -> 8 -> 9 -> null

 3: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 3: 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9 -> null

 4: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 4: 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> 9 -> null

 5: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 5: 1 -> 2 -> 3 -> 5 -> 7 -> 8 -> 9 -> null

 6: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 6: 1 -> 2 -> 4 -> 5 -> 6 -> 8 -> 9 -> null

 7: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 7: 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9 -> null

 8: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 8: 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null

 9: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
 9: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

删除单链表首尾的第n个节点

Delete nth node from both beginning and end of singly linked list

c++

algorithm

linked-list

singly-linked-list

pseudocode