加米, lc82的细节讨论 Remove Duplicates from Sorted List II

麻烦帮我看一下这个题，会尽力为大家加米，谢谢。
-----------------------题目描述-------------------------------------------------
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:



我的疑问是：

我用下面代码的逻辑在python3里写了一遍，运行出来的结果是[1,2,3,5]；我认为在第20行slow.next = fast.next;， slow已经指向了3，所以3被保留在了结果中。感觉这个逻辑是不对的，为什么Java的结果通过了呢？
-------------------accepted Java代码----------------------------------

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. public class Solution {
   
10.     public ListNode deleteDuplicates(ListNode head) {
    
11.         //use two pointers, slow - track the node before the dup nodes,
    
12.         // fast - to find the last node of dups.
    
13.         ListNode dummy = new ListNode(0), fast = head, slow = dummy;
    
14.         slow.next = fast;
    
15.         while(fast != null) {
    
16.             while (fast.next != null && fast.val == fast.next.val) {
    
17.                 fast = fast.next;    //while loop to find the last node of the dups.
    
18.             }
    
19.             if (slow.next != fast) { //duplicates detected.
    
20.                 slow.next = fast.next; //remove the dups.
    
21.                 fast = slow.next;     //reposition the fast pointer.
    
22.             } else { //no dup, move down both pointer.
    
23.                 slow = slow.next;
    
24.                 fast = fast.next;
    
25.             }
    
26. 
    
27.         }
    
28.         return dummy.next;
    
29.     }
    
30. }

复制代码

------wrong answer python 3 code--------------

1. # Definition for singly-linked list.
   
2. # class ListNode:
   
3. #     def __init__(self, x):
   
4. #         self.val = x
   
5. #         self.next = None
   
6. 
   
7. class Solution:
   
8.     def deleteDuplicates(self, head: ListNode) -> ListNode:
   
9.         dummy = ListNode(0);
   
10.         slow = dummy;
    
11.         fast = head;
    
12.         slow.next = fast;
    
13.         while (fast):
    
14.             while (fast.next and fast.val == fast.next.val) :
    
15.                 fast = fast.next;
    
16.             
    
17.             if (slow.next.val != fast.val):
    
18.                 slow.next = fast.next;
    
19.                 fast = slow.next;
    
20.             else:
    
21.                 slow = slow.next;
    
22.                 fast = fast.next;
    
23.         return dummy.next;

复制代码

上面判断的是slow.next是不是fast，但是下面判断的是slow. next. val是不是fast. val，仔细想想，其实两者有区别。打个比方，如果1-2-3-3-4-4-5的时候，当slow在2那里，fast会停在第二个3，但是这个时候slow. next. val和fast. val是相等的，slow移向下一个3。这个时候，3就在你的返回值里面了。手机码字，不知道是不是清楚。

我实话我感觉这样的题面试不太可能会考 我自己suppose的

plugin1689 发表于 2019-12-27 11:13
我实话我感觉这样的题面试不太可能会考 我自己suppose的

为什么呢？太简单了吗还是考察的点太直接？

Java的代码没问题，fast指针始终在slow前一位，slow=2的时候fast=3，所以就把3的dupremove掉了。你Python的代码和Java逻辑不是完全一样的，在Pyhton17行if (slow.next.val != fast.val)，直接比较值的话，slow=2,fast=3，那么这里slow.next 就等于第二个3了。后面这个3就到答案里面去了。Java20行比的是地址，即使是两个3也是不相等的。

不知道小帅 发表于 2019-12-27 11:56
上面判断的是slow.next是不是fast，但是下面判断的是slow. next. val是不是fast. val，仔细想想，其实两者 ...

谢谢，第一句话就点明了关键，说的很清楚。我现在明白啦！ 应该是我对linked list的理解不到位，总是忽略listnode的链接特性，老想着node的具体value。

还有一个问题想请教，下面这种解法里pre.next = None;是自己怎么也想不到的，对linkedlist指来指去，什么留在要返回的链表里总是想不清楚。有没有什么建议呢？谢谢。

1.     def deleteDuplicates(self, head):
   
2.         dummy = ListNode(0);
   
3.         pre = dummy;
   
4.         cur = head;
   
5.         real = dummy;
   
6. 
   
7.         while (cur):
   
8.             if (pre == dummy or pre.val != cur.val) and (cur.next == None or cur.val != cur.next.val ):
   
9.                 real.next = cur;
   
10.                 real = cur;
    
11.                 pre = cur;
    
12.                 cur = cur.next;
    
13.                 pre.next = None;
    
14. 
    
15.             else :
    
16.                 pre = cur;
    
17.                 cur = cur.next;
    
18.                 pre.next = None;
    
19.         return dummy.next;

复制代码

WarriorZ 发表于 2019-12-27 12:15
Java的代码没问题，fast指针始终在slow前一位，slow=2的时候fast=3，所以就把3的dupre ...

谢谢，说的非常清楚～

超人96825 发表于 2019/12/27 12:23:48
谢谢，第一句话就点明了关键，说的很清楚。我现在明白啦！ 应该是我对linked list的理解不到位，总是忽略listn...

我觉得就自己拿纸多画一下吧。Linked list有时候还是很tricky的。自己画一下，考虑一下有没有corner case。

超人96825 发表于 2019/12/27 12:23:48
谢谢，第一句话就点明了关键，说的很清楚。我现在明白啦！ 应该是我对linked list的理解不到位，总是忽略listn...

还有就是用多个指针的话，一定要搞清楚指针的意义，哪个是返回值，快慢指针意义是什么。然后这个题目是有一些invariant的，不论何时都成立的。要保证每一步都是成立的。