I'm just starting to learn linkedlist.

I can come up with an approach to delete a nth node from the beginning and end separately but I couldn't take care of the checks needed to perform both at the same time.

Delete nth node from both beginning and end

INPUT:

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

OUTPUT:

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

C program or a general algorithm would be much appreciated.

CodePudding user response：

Suppose you are at node 3.

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

So basically you need to get to the node after the one you seek to delete prior to that deletion as then there will be no way of accessing it.

To check if there are any nodes at all:

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

If there are nodes:

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

Notice that if you delete node n and you are still at node (n-1), you will just have to do a seperate "shift of indicies," so to say, to remove another node. So if you want to delete another node that was previously the pth one, then just do in the if statement

///the deletion
  count;

Effectively you will get count == p when you arrive at the node that was the pth one until any deletions.

CodePudding user response：

The task is not simple for such beginners as you and me.

Nevertheless, we, beginners, should help each other.

For starters indices in C start from 0.

Secondly you should check whether the pointer starting from the tail is equal to the pointer starting from the head. Or whether one pointer is the pointer of the data member next of the node pointed to by other pointer.

For example if the two pointers are equal each other you need to delete only one node in the list.

I can not write a pseudo code so here you are

#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';
    }
}

The program output is

 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