给定一个已排序的链表,删除所有具有重复数字的节点,只留下与原始列表不同的数字。
示例:
给予
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;
}
}
在不改变程序功能的情况下,
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
从未动过,它留在原处,这就是dummy
。 prev.next
指向 3,我们错误地返回了它。
请注意,如果输入较长,例如 1, 1, 1, 2, 3, 4, 5, 6,
同样的行为还会继续下去
prev.next
继curr
之后,
并且实现会错误地返回 6 -> null
。
算法被破坏了。
考虑这个替代算法:
head
作为下一个(就像你已经做的那样)next.val
和 next.next.val
next.val
next
和next.next
(设置在next.next.next
旁边)val
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;
public static ListNode deleteDuplicates(ListNode head) {
// do nothing if the list is empty
if (head == null) {
return null;
}
ListNode current = head;
// compare the current node with the next node
while (current.next != null) {
if (current.data == current.next.data)
current.next = current.next.next;
else
current = current.next; // only advance if no deletion
}
return head;
}