Remove Duplicates from Sorted List II

今天是一道有关链表的题目，来自LeetCode，难度为Medium，Acceptance为27%。

题目如下

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

解题思路及代码见阅读原文

回复0000查看更多题目

解题思路

首先，该题是Remove Duplicates from Sorted List 的升级版，难度略有加大，但是其实也并不难。区别是，在Remove Duplicates from Sorted List一题中，是对重复的数字只保留一个，这里是一个都不保留。

然后，了解是上述区别，应该如何改变算法呢：

• 在Remove Duplicates from Sorted List一题中我们这样做，用一个指针遍历整个链表，如果要保留一个数字，则用这个指针指向的节点和已经加入结果列表的尾节点比较，如果相同则跳过；

• 在本题中我们不保留重复的节点，那么我们可以用如下方法：

1.首先用一个循环跳过相同的节点；

2.用该节点和已经加入链表的尾节点的下一个节点比较，如果相同则加入链表；

3.如果不同，则跳过该节点。

好了，有了上述思路，下面我们来看代码。

代码如下

Java版

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list
     * @return: ListNode head of the linked list
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        if(null == head)
            return null;
        ListNode newHead = new ListNode(0), p = newHead, fast = head;
        newHead.next = head;
        while(fast != null) {
           while(fast.next != null && fast.val == fast.next.val) {
               fast = fast.next;
           }
           if(p.next == fast) {
               p = p.next;
           } else {
               p.next = fast.next;
           }
           fast = fast.next;
        }
        p.next = null;
        return newHead.next;
    }
}

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image