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

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。

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

到此结束。prev没有移动，它一直呆在原地，也就是dummy。prev.next指向3，我们返回的是错误的。注意，如果输入较长，例如1,1,1,2,3,4,5,6，同样的行为还会继续，curr之后的prev.next，实现会错误地返回6 -> null。算法被破坏了

---

考虑这个替代算法:

1. 创建一个虚拟节点，指向head作为下一个(就像你已经做的那样)
2. 设置当前节点为虚拟
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;