删除单链表开头和结尾的第n个节点

Question

我刚开始学linkedlist。

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

从开始和结束处删除第n个节点

输入:

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

输出:

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

DELETE FROM begin:

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);

}

DELETE FROM END:

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