整个问题的解题思路如下:
建立指针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次方)