咨询一道链表去重问题

题目在这里82. Remove Duplicates from Sorted List II我觉得这个和string去重思路是一样的，重复的一个也不留，这个是string的写法：

1. public String deDup(String input) {
   
2. 
   
3.    //corner case
   
4. 
   
5.    if(input==null || input.length()<=1) return input;
   
6.    char[] array = input.toCharArray();
   
7.    int end=0; //the top of stack
   
8.    for(int i=1;i<array.length;i++){
   
9.         if(end == -1 || array[i]!=array[end]){
   
10.             array[++end] = array[i]; //日常拷贝
    
11.         }else{
    
12.             end--;
    
13.             while(i+1<array.length && array[i]==array[i+1]){
    
14.                 i++;
    
15.             }
    
16.        }
    
17.     }
    
18.     return new String(array,0,end+1);
    
19. }

复制代码

所以我觉得相同的思路，这个链表也能写，所以就有了：

1. public ListNode deleteDuplicates(ListNode head) {
   
2.         if(head == null) return head;
   
3.         ListNode slow = head;
   
4.         ListNode fast = head;
   
5.         //here should be dummy head
   
6.         ListNode dummy = new ListNode(-1);
   
7.         dummy.next = head;
   
8.         // here should have dummy && pre node of slow
   
9.         ListNode prev = head;
   
10.       
    
11.         while(fast!= null){
    
12.             if(slow.val != fast.val){
    
13.                 prev.val = slow.val;
    
14.                 slow = slow.next;
    
15.                 slow.val = fast.val;
    
16. 
    
17.             }else{
    
18.                
    
19.                 slow = prev; //死循环，而且还不能任意改动.val值
    
20.                 while(fast.next!=null && slow.val == fast.val){
    
21.                     fast = fast.next;
    
22.                 }
    
23.             }
    
24.         }
    
25.         //断点
    
26.         slow.next = null;
    
27.         return dummy.next;
    
28.     }

复制代码

可是我发现，换成链表了要不就是slow!=null || 不能加，要么就会陷入死循环
不知道该如何处理prev(对应end--)这个操作
在list中引入prev，这样写会在出现NPE      

1. if(slow!=null|| slow.val != fast.val){
   
2.                 prev = slow;
   
3.                 slow = slow.next;
   
4.                 slow.val = fast.val; //here

复制代码

然后这样改动还会死循环：

1. }else{         
   
2.                 slow = prev; //死循环,因为slow永远=prev
   
3.                 while(fast.next!=null && fast.val == fast.next.val){
   
4.                     fast = fast.next;
   
5.                 }

复制代码

想了一天，问了一天了，实在没办法po在地里了，希望大佬们指点迷津
就是按照string那个思路来走，对应着链表中，应该怎么改呢

我觉得你可以尝试先理清你的slow/fast/prev三个变量分别代表什么。
你一开始就把它们全指向了head，这种情况下你的dummy的意义是什么？

附上我的solution以供参考

1. class Solution {
   
2.     public ListNode deleteDuplicates(ListNode head) {
   
3.         if (head == null) return null;
   
4.         ListNode pseudo = new ListNode(0);
   
5.         pseudo.next = head;
   
6.         
   
7.         ListNode taken = pseudo;
   
8.         ListNode begin_seg = head;
   
9.         ListNode curr = head.next;
   
10.         
    
11.         while(true) {
    
12.             boolean dup = false;
    
13.             while (curr != null && begin_seg.val == curr.val) {
    
14.                 curr = curr.next;
    
15.                 dup = true;
    
16.             }
    
17.             if (dup) {
    
18.                 taken.next = curr;
    
19.             } else {
    
20.                 taken = begin_seg;
    
21.             }
    
22.             if (curr == null) {
    
23.                 return pseudo.next;
    
24.             } else {
    
25.                 begin_seg = curr;
    
26.                 curr = curr.next;
    
27.             }
    
28.         }
    
29.     }
    
30. }

复制代码