java从排序的链表中删除重复的节点。为什么我的输出是错误的？

Question

给定一个已排序的链表，删除所有具有重复编号的节点，只留下与原始列表不同的编号

例如：

• 给定1->2->3->3->4->4->5->null，返回1->2->5->null

• 给定1->1->1->2->3->null，返回2->3->null

问题：

• 给定1->1->1->2->3->null，我下面的解决方案return 3->null

有人能告诉我为什么吗

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param ListNode head is the head of the linked list
     * @return: ListNode head of the linked list
     */
    public static ListNode deleteDuplicates(ListNode head) {
        // write your code here
        if(head == null || head.next == null) return head;

        ListNode post = head.next;
        ListNode curr = head;
        ListNode dummy = new ListNode(head.val-1);  // make sure dummy node value is different from the head
        dummy.next = head;
        ListNode prev = dummy;

        while(post != null) {
            //System.out.println("prev.val = " + prev.val + ", curr.val = " + curr.val + ", post.val = " + post.val + ", prev.next.val = " + prev.next.val);   
            //System.out.println("prev.next.val = " + prev.next.val + ", curr.next.val = " + curr.next.val);            

            if(prev.next.val == curr.val && prev.next.val == post.val) {
                curr = curr.next;
                post = post.next;
            }
            else if(prev.next.val == curr.val && prev.next.val != post.val) {
                curr = curr.next;
                post = post.next;                
                prev.next = curr;
            }
            else {
                prev = prev.next;
                curr = curr.next;
                post = post.next;
            }
        }

        return dummy.next;
    }
}

Answer 1

在不改变程序功能的情况下， 可以将while循环转换为更可读的形式：

while (post != null) {
    if (prev.next.val != curr.val || prev.next.val != post.val) {
        if (prev.next.val == curr.val) {
            prev.next = curr.next;
        } else {
            prev = prev.next;
        }
    }
    curr = curr.next;
    post = post.next;
}

这相当于您的实际代码。 我会根据这个版本来解释， 因为我觉得这更容易阅读和推理

让我们观察几件事：

• 在开头，prev.next指向curr。 所以prev.next.val等于curr.val。 而且，post比curr领先一步

• curr与post一起移动。 curr和post在if条件内没有改变， 作为循环的最后一步， 他们都向前推进一个位置

考虑到输入1、1、1、2、3和上述观察结果：

• 外部if条件将为假，直到post达到2

• curr落后一步，所以它指向2之前的1

• prev没有移动，所以prev.next仍然指向第一个1

• 所以在这一点上，prev.next.val等于curr.val（都是1）， 但它不等于post.val，也就是2。 所以我们进入了外部的if

• 作为prev.next.val == curr.val，我们也输入内部if， 并设置prev.next = curr.next。 请记住，循环的最后一步是将curr前进到curr.next。 所以prev.next将指向curr

• 在下一次迭代中，我们在3处有post，在2处有curr，并且prev.next指向curr。因此，我们输入另一个if，然后输入内部if，将prev.next设置为curr.next，即3

这就是结局prev从未移动过，它呆在原地，也就是{}prev.next指向3，我们返回的是错误的。 请注意，如果输入较长，例如1、1、1、2、3、4、5、6， 同样的行为还会继续， prev.next在{}之后， 而实现将错误地返回6 -> null。 算法被破坏了

---

考虑这种替代算法：

1. 创建一个虚拟节点，指向head作为下一个节点（正如您已经做的那样）
2. 将当前节点设置为dummy
3. 而下一个节点存在，下一个节点存在
   • 比较next.val和next.next.val
   • 如果不相等，则前进当前节点
   • 如果相等，则：
     • 保存next.val的副本
     • 跳过next和next.next（设置在next.next.next旁边）
     • 跳过所有值等于已保存val的节点
4. 返回dummy.next

像这样：

if (head == null) return head;

ListNode dummy = new ListNode(head.val - 1);
dummy.next = head;

ListNode node = dummy;
while (node.next != null && node.next.next != null) {
    if (node.next.val != node.next.next.val) {
        node = node.next;
    } else {
        int val = node.next.val;
        node.next = node.next.next.next;
        while (node.next != null && node.next.val == val) {
            node.next = node.next.next;
        }
    }
}

return dummy.next;