卖萌的弱渣

I am stupid, I am hungry.

Remove Duplicates From Sorted List II

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.

Solution

  • Java
(Remove-Duplicates-from-Sorted-List2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode newhead = new ListNode(-1);
        newhead.next = head;
        ListNode prev = newhead;
        ListNode cur = head;

        while(cur!=null){
            while(cur.next!=null && cur.next.val == cur.val)
                cur = cur.next;
            // 只有这种情况cur才会被真正加入newheadlist中
            if(prev.next == cur)
                prev = prev.next;
            else// 此时还无法判断cur.next是不是重复
                prev.next = cur.next;
            cur = cur.next;

        }
        return newhead.next;

    }
}
  • Python
  • New list only contains the node without duplicates in the old list.
(Remove-Duplicates-from-Sorted-List2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

 class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        node = ListNode(-1)
        ret = node
        while head != None:
            nextNode = head.next
            # find next node
            if nextNode != None and nextNode.val == head.val:
                while nextNode != None and nextNode.val == head.val:
                    nextNode = nextNode.next
            else:
                # found non-duplicated nodes
                node.next = head
                node = head
                # in case there is no other node
                node.next = None

            head = nextNode
        return ret.next