单链表删除重复结点

用单链表保存m个整数,结点的结构为(data,next)且|data|<=n(n为正整数)。现在要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。

public class E2 {
    static class Node {
        int data;
        Node next;
    }
    private static Node createLinked() {
        System.out.println("请输入结点个数");
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Node head = new Node();
        head.next = null;
        Node r = head;
        while (n-- > 0) {
            Node e = new Node();
            e.data = scanner.nextInt();
            e.next = null;
            r.next = e;
            r = e;
        }
        return head;
    }

    private static Node deleteRepeatNode(Node l) {
        //获得首元结点
        Node p = l.next;
        while (p != null) {
            //用于获得待删除结点的前驱结点
            Node p1 = p;
            Node p2 = p.next;
            while (p2 !=null) {
                if (p2.data == p.data) {
                    p1.next = p2.next;
                    p2 = p2.next;
                }
                else {
                    p2 = p2.next;
                    p1 = p1.next;
                }
            }
            p = p.next;
        }

        return l;
    }

    public static void main(String[] args) {
        Node linked = createLinked();
        Node node = deleteRepeatNode(linked);
        Node p = node.next;
        while (p != null) {
            System.out.println(p.data);
            p = p.next;
        }
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容