码疯窝

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

算法分析: 与前一篇文章处理方法一样的, 唯一的不同是, 上一篇只是重复的元素只保留一个, 这题目是, 重复元素全部删除, 所以没法在第一次循环中知道, 哪些是需要删除的..

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        HashMap keys = new HashMap();
        
        ListNode tmp = head;
        while (tmp != null) {
            keys.put(tmp.val, keys.containsKey(tmp.val));
            tmp = tmp.next;
        }
        ListNode n = new ListNode(0);
        n.next = head;
        
        ListNode parent = n;
        ListNode child = parent.next;
        while(parent != null && child != null) {
            if (keys.containsKey(child.val) && keys.get(child.val)) {
                parent.next = parent.next.next; 
            } else {
                parent = parent.next;
            }
            child = parent.next;
        }
        return n.next;
    }
}

C++:

 

Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def deleteDuplicates(self, head):
        keys = {}
        tmp = head
        while (tmp != None):
            keys[tmp.val] = keys.has_key(tmp.val)
            tmp = tmp.next
        n = ListNode(0)
        n.next = head
        parent = n
        child = n.next
        
        while (parent != None and child != None):
            if (keys[child.val]):
                parent.next = parent.next.next
            else:
                parent = parent.next
            child = parent.next
        
        return n.next
                
        
继续查看有关 日志连载的文章

2个访客评论

  1. 尚吾网

    爱你不是两三天,每月看你很多遍。

    qweqwe Reply