题解 | #删除有序链表中重复的元素-II#

思路

下文均以nex代表当前遍历结点，now为初始时nex的上一结点

1. 处理头部重复结点（注意头部可能有多个重复结点）

• 当head和head.next的val相等时：找到不相等的值或者now.next为null
  • 若为值不相等，则令nex为新头节点，继续循环判断
  • 若为null（此时值相等），说明所有结点都为重复值，则返回null

2. 处理非头部重复结点
   • 用las记录now的上一个结点，nex遍历，找到与now不相等的值或者nex为null
   • 若值不相等且now与nex相邻，说明此处无重复元素、更新las、now、nex位置，继续循环判断
   • 若值不相等且now与nex不相邻，说明从now到nex的上一个结点均为重复值，令las.next=nex,更新las、now、nex位置，继续循环判断
   • 若为null（值仍然相等）说明从now到末尾均为重复值，令las.next=null，返回head

代码

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode now=head;
        ListNode las=now;
        ListNode nex=now.next;
        //处理头部重复结点
        while(head.next!=null&&head.val==head.next.val){
            while(head.next!=null&&head.val==head.next.val){
                head=head.next;
            }
            if(head.next==null) return null;
            if(head.val!=head.next.val) head=head.next;
        }
        //处理非头部重复节点
        while(nex!=null){
            while(now.val==nex.val&&nex.next!=null){
                nex=nex.next;
            }
            if(now.val!=nex.val){
                if(now.next==nex){
                    las=now;
                    now=nex;
                    nex=nex.next;
                }
                else{
                    las.next=nex;
                    now=nex;
                    nex=nex.next;
                }
            }
            else{
                if(las==now) return null;
                las.next=null;
                return head;
            }
        }
        return head;
    }
}