首页 > 代码库 > Cracking the Coding Interview Q2.1

Cracking the Coding Interview Q2.1

Write code to remove duplicates from an unsorted linked list.

FOLLOW UP

How would you solve this problem if a temporary buffer is not allowed?

 

思路1:用hashset存储已经出现的节点,如果重复则删除。空间O(N),时间O(N)。

思路2:两个指针,对于每个当前节点,遍历后面的元素删除重复。 空间O(1),时间O(n^2)。

思路3:移动窗口法是否可行?

 

    public static void deleteDupsA(LinkedListNode n) {        HashSet<Integer> set = new HashSet<Integer>();        LinkedListNode previous = null;        while (n != null) {            if (set.contains(n.data)) {                previous.next = n.next;            } else {                set.add(n.data);                previous = n;            }            n = n.next;        }    }        public static void deleteDupsC(LinkedListNode head) {        if (head == null) return;        LinkedListNode previous = head;        LinkedListNode current = previous.next;        while (current != null) {            // Look backwards for dups, and remove any that you see.            LinkedListNode runner = head;            while (runner != current) {                 if (runner.data =http://www.mamicode.com/= current.data) {                    LinkedListNode tmp = current.next;                    previous.next = tmp;                    current = tmp;                    /* We know we can‘t have more than one dup preceding                     * our element since it would have been removed                      * earlier. */                    break;                }                runner = runner.next;            }                        /* If runner == current, then we didn‘t find any duplicate              * elements in the previous for loop.  We then need to              * increment current.               * If runner != current, then we must have hit the ?break?              * condition, in which case we found a dup and current has             * already been incremented.*/            if (runner == current) {                previous = current;                current = current.next;            }        }    }        public static void deleteDupsB(LinkedListNode head) {        if (head == null) return;                LinkedListNode current = head;        while (current != null) {            /* Remove all future nodes that have the same value */            LinkedListNode runner = current;            while (runner.next != null) {                 if (runner.next.data =http://www.mamicode.com/= current.data) {                    runner.next = runner.next.next;                } else {                    runner = runner.next;                }            }            current = current.next;        }    }