关于链表的删除操作
要删除拥有最大值的数据项,需要遍历多少次单链表?
[解决办法]
如果只是删除最大的一个,不考虑重复的情况则只需要一遍就行了。但是要考虑重复的情况就要看最大的数有多少个,就需要视情况而定了,若表有序,则只需要一遍;若表无序,一般的算法,则需要用最大的数的实际个数那么多次,如果在设计程序时,就采用一个额外的存贮空间来记录这个最大的数的位置,则也只需要一遍就可以了。
[解决办法]
若表无序,
如果在设计程序时,就采用一个额外的存贮空间来记录这个最大的数的位置,则也
只需要一遍就可以了。
如果在设计程序时,并不知道最大的数值,则第一次遍历就要找到最大数值,
然后第二次遍历,进行删除工作;
这种方法比较方便也可行。
如果在设计程序时,并不知道最大的数值,也可以通过拆分单链表的方法。即将数值相同的
结点连接成一个单独的单链表,并且只需记录每个链表中的第一个结点
数值就可以了,这种方法可以只遍历一次链表,但操作起来麻烦一些,
并且改变了过去元素之间的逻辑关系。
[解决办法]
如果没有重复值, 只需要遍历一遍, 使用两个节点指针, 一个进行遍历, 另一个指向当前已发送的最大值. 如果有重复值, 指向最大节点的指针再遍历到末尾. 两者最坏情况遍历两次.