首页 > 代码库 > 【Leetcode】Remove Duplicates from Sorted List in JAVA

【Leetcode】Remove Duplicates from Sorted List in JAVA

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.

思路很简单,由于乖乖的sort好了,就是判断下一个是不是比它大就好了,如果大,那么跳过下一个直接link到下一个的下一个。但是此时注意,考虑如果是1->1->1这种情况,当你把第二个1删掉之后,指针一定要保留在第一个的位置,这样才可以接着判断这个1与再下一个1是不是相等(即第一个1和第3个1)。唯一需要格外注意的情况就是最后两个,由于你要p.next=p.next.next来删除,所以对于最后两个不存在next的next,所以直接等于null就好啦

package testAndfun;


public class deleteDuplicates {
	public static void main(String args[]){
		deleteDuplicates dp = new deleteDuplicates();
		ListNode head  = new ListNode(3);
		ListNode p1 = new ListNode(3);
		head.next=p1;
		ListNode p2  = new ListNode(3);
		p1.next =  p2;
		ListNode p3 = new ListNode(3);
		p2.next = p3;
		ListNode p4 = new ListNode(13);
		p3.next = p4;
		prinf(head);
		prinf(dp.deleteDup(head));
	}
	
	private static void prinf(ListNode input){
		while(input!=null)	{
			System.out.print(input.val+"->");
			input = input.next;
		}
		System.out.println();
	}
	
	public ListNode deleteDup(ListNode head){
		if(head==null||head.next==null)	return head;//if no head, what should I do?
		ListNode p=head;
		int i=0;
		//System.out.println(p.val+" and "+p.next.val);
		while(p.next != null){
			if(p.val==p.next.val&&p.next.next!=null)	{
				//System.out.println("go first"+p.val);//"^^"+p.next.val+"%%"+p.next.next.val);
				p.next=p.next.next;
				continue;//if this and next equal, we should stay in this in case next.next is equal this
			}
			else if(p.val==p.next.val&&p.next.next==null)	{
				//System.out.println("go second"+p.val);
				p.next=null;
				continue;
			}
			//System.out.println(p.val+" round "+i++);
			p=p.next;
			if(p==null)	break;
		}
		//System.out.print(head.val);
		return head;
	}

}


【Leetcode】Remove Duplicates from Sorted List in JAVA