LeetCode-Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List II

##题目

####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.

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

##解题思路
该题与Remove Duplicates from Sorted List非常类似，同样是去除链表中的重复元素，但是这里不保留重复的元素，还是链表操作，这里定义三个指针k,i,j往后推进。指针i，j之间是重复的元素(包含i,但不包含j)，k是i的前一位指针，然后通过k.next=j来进行跳过所有的重复元素，同时i=j,j=j.next.依次下去，直到j=null为止。由于只要遍历链表一遍，所以时间复杂度为O(n)。

这里有个注意点，为了初始化k指针，这里重创了一个新的头结点newhead,然后将这个节点的next指向head节点.

##算法代码
代码采用JAVA实现：

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 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) {
        if(head==null || head.next==null)
        	return head;
        ListNode newhead=new ListNode(-1);
        newhead.next=head;
        ListNode i=head;
        ListNode j=head.next;
        ListNode k=newhead;
        while(j!=null)
        {
        	while(j!=null && i.val==j.val)
        	{
        		j=j.next;
        	}
        	if(j!=null)
        	{
        	    if(i.next!=j)
            	{
            		k.next=j;
    	        	i=j;
    	        	j=j.next;
            	}else{
            		j=j.next;
            		i=i.next;
            		k=k.next;
            	}	
        	}else{
        	    k.next=j;
        	}
        	
        }
        return newhead.next;
    }
}

Comments

▲