package Leetcode.list;

import java.util.LinkedList;

/**

* @author zbl

* @version 1.0

* @content:给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5

输出: 1->2->5

示例 2:

输入: 1->1->1->2->3

输出: 2->3

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

* @date 2020/7/21 22:35

*/

public class Solution82 {

public static class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

}

}

public static ListNode deleteDuplicates(ListNode head) {

if(head==null || head.next==null) return head;

LinkedList<ListNode>list=new LinkedList<>();

ListNode cur=head;

while(cur!=null){

if(list.isEmpty() || list.peekLast().val!=cur.val){

list.add(cur);

cur=cur.next;

}else{

while(cur!=null && list.peekLast().val==cur.val){

cur=cur.next;

}

list.pollLast();

if(!list.isEmpty())list.peekLast().next=null;//断开list中最后一个元素与原来元素的连接关系

}

}

if(list.isEmpty()) return null;

ListNode newhead=list.pollFirst();

ListNode next=newhead;

while(!list.isEmpty()){

next.next=list.pollFirst();

next=next.next;

}

return newhead;

}

public static ListNode deleteDuplicates2(ListNode head) {

if(head==null || head.next==null) return head;

ListNode cur=head,pre=null,prepre=null;

boolean flag=false;//表示 是否找到了头结点

ListNode newHead=null;

while(cur!=null){

if(cur!=cur.next){

if(!flag){

newHead=cur;

flag=true;

}

prepre=pre;

pre=cur;

cur=cur.next;

}else{

if(pre!=null) pre.next=null;//断开连接

while(cur!=null && cur==cur.next){

cur=cur.next;

}

if(cur!=null){

ListNode tmp=cur.next;

cur.next=null;//断开连接

cur=tmp;

if(pre!=null) pre.next=cur;

}

}

}

return newHead;

}

public static void main(String[] args) {

ListNode head=new ListNode(1);

head.next=new ListNode(2);

head.next.next=new ListNode(2);

deleteDuplicates(head);

}

}