wsh_wshkk 2023-10-19 20:32 采纳率: 70%
浏览 106

数据结构 删除链表中绝对值相等的结点

本关任务:利用单链表表示一个整数序列,实现一个时间复杂度为O(n)的算法,对于链表中绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。

输入
多组数据,每组数据有两行,第一行为链表的长度n,第二行为链表的n个元素(元素之间用空格分隔)。当n=0时输入结束。

输出
对于每组数据分别输出一行,依次输出删除结点后的链表元素,元素之间用空格分隔。

测试输入:
5
21 -15 -15 -7 15
7
90 32 -90 -66 77 66 90
0

预期输出:
21 -15 -7
90 32 -66 77

#include <iostream>
using namespace std;
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode, * LinkList;
void CreateList_R(LinkList& L, int n)
{//后插法创建单链表
    L = new LNode;
    L->next = NULL;
    LinkList r = L;
    for (int i = 0; i < n; i++)
    {
        LinkList p = new LNode;
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}
void PrintList(LinkList& L)
{//打印依次输出链表中的数据
    L = L->next;
    while (L) {
        if (L->next != NULL) cout << L->data << " ";
        else cout << L->data;
        L = L->next;
    }
    cout << endl;
}
int Abs(int x)
{//绝对值函数
    return x > 0 ? x : -x;
}
void DeleteEqualNode(LinkList& L, int n)
{//删除链表中绝对值相等的结点
/**************begin************/
    LinkList p = L->next;
    LinkList t = p->next;
    LinkList u = p;
    for (int i = 1; p->next!=NULL; i++)
    {

        for (int j = i; u->next != NULL; j++)
        {
            
            if (p->data == t->data || p->data * -1 == t->data)
            {
                if (t->next == NULL)
                {
                    u->next = NULL;
                    LinkList a = t;
                    t = t->next;
                    delete a; 
                }
               
            }
            else
            {
                t = t->next;
                u = u->next;
            }
        }
        p = p->next;
        u = p;
        t = p->next;
    }




/**************end************/
}
int main()
{
    int n;
    while (cin >> n)
    {
        if (n == 0) break;
        LinkList L;
        CreateList_R(L, n);
        DeleteEqualNode(L, n);
        PrintList(L);
    }
    return 0;
}

img


这个是代码块,这个循环停不下来,要怎么改呀

  • 写回答

2条回答 默认 最新

  • 真相重于对错 2023-10-19 20:43
    关注

    使用hash表

    评论

报告相同问题?

问题事件

  • 创建了问题 10月19日