【题目描述】
Given a sortedlinked list, delete all nodes that have duplicate numbers, leaving only distinct numbersfrom 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.
【编程步骤】
* 1. 处理特殊情况:如果该链表为空或只有一个结点,说明此链表没有重复的元素,直接返回头指针head;
即:if(head==null||head.next==null)
return head;
* 2. 设置伪头结点;
即:ListNode pre=new ListNode(0);
pre.next=head;
head=pre;
* 3. 令cur=pre.next,若不存在复本,cur依然为pre.next;若存在复本,cur指向复本的下一个不等于它本身值的结点,并作移除操作;
ListNode cur=pre.next; while(cur.next!=null&&cur.next.val==cur.val) cur=cur.next; if(pre.next==cur){ // don't find the duplicate pre=pre.next; }else{ //remove the duplicate node pre.next=cur.next; }
* 4. 返回head.next,因为此时的head为伪头结点;
【代码实现】
/** * 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 pre=new ListNode(0); pre.next=head; head=pre; while(pre.next!=null){ ListNode cur=pre.next; while(cur.next!=null&&cur.next.val==cur.val) cur=cur.next; if(pre.next==cur){ // don't find the duplicate pre=pre.next; }else{ //remove the duplicate node pre.next=cur.next; } } return head.next; } }