线性表之单链表应用(2)

整个问题的解题思路如下:

建立指针p,用于遍历链表;

建立指针q,q遍历p后面的结点,并与p数值比较;

如果q与p值相等,则删除q。如果q有后继节点,则将q前驱节点和q后继节点链接起来;否则直接开始下一轮遍历。

Java代码实现如下,建议将这段代码copy到之前的Java版本的LinkedList(FOLinkedList)中。

/** * @TODO 重复节点的删除 * @param foll 需要删除重复节点的单链表 * @return foll 删除重复节点后的单链表 */ public static FOLinkedList removeRepeatElement(FOLinkedList foll){ FOLinkedNode p = foll.header; if(foll.header==null){ return foll; } while(p.next!=null){ FOLinkedNode q = p.next; while(q.next!=null){ if(q.next.getE().equals(p.getE())){ q.addNext(q.next.next); foll.size--; }else{ q = q.next; } } p=p.next; } return foll; }

算法的时间性能为O(n的2次方)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/ddf371bd228b2c3366dfde0ceb14722f.html