删除链表重复元素的问题

世界级白日梦冠军

2024-04-24 帮助1人

一、删除所有重复元素，使每个元素只出现一次

一、删除所有重复元素，使每个元素只出现一次

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

学新通

1.1带头链表解法

首先，我们要排除链表为空的情况。另一种可以直接返回的情况就是头结点的后继节点为空，如果只有一个结点那么肯定不存在重复元素的问题，所以以上两种情况可以直接返回head。

如何能知到哪个节点是重复结点，判断这一点一定会牵扯到两个结点之间的比较，如果prev.val == cur.val name说明prev和cur是两个重复的节点。

所以我们要创建一个带头链表dummyHead，使他的第一个数为-101（其实为多少都可以，因为这个结点是不进入循环判断的，判断的是他的后继节点）然后让dummyHead.next = head，使自己创建的带头链表和给的单链表做出联系。

已经判断过head和head.next非空，则使prev = dummyHead.next并且cur = prev.next。

学新通

prev指向的可以是第一个重复的节点，因为要保存它，也可以指向不重复的结点。cur就是要和prev判断的结点，如果两个值相等那么cur和prev.next就需要向后移，这个时候中间重复的结点就已经被删除了，这个过程会一直进行到cur和prev不再相等。

学新通

当移动到不相等的时候，prev 就可以移动了prev= prev.next，然后cur = cur.next，继续进行下一次判判断

学新通

最后只要返回dummyHead.next就能返回没有重复元素的链表了。

public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode dummyHead = new ListNode(-101);
dummyHead.next = head;
ListNode prev = dummyHead.next;
ListNode cur = prev.next;
while (cur != null) {
if(prev.val == cur.val) {
prev.next = cur.next;
}else {
prev = prev.next;
}
cur = cur.next;
}
return dummyHead.next;
}

也可以直接使用单链表解法，不需要创建一个单独的虚拟头结点直接将prev指向head即可，其他相同。

1.2 递归方法

首先，也是要看链表为空的和头结点的后继节点为空的两种情况，此时不可能存在重复节点，直接返回链表的头结点即可。即是递归的结束条件也是特殊情况。

然后需要先处理子链表，则让head.next = deleteDuplicates(head.next)，由方法来判断head.next是哪个结点。

现在就可以处理当前头节点的情况，如果 head.val == head.next.val则return 第二个节点，第一个结点就直接删除了，只保留了一个重复地结点。如果不相等那么return 第一个结点，然后第二个结点留着继续判断。

递归进行到最后是这样的，head.next==null。

学新通

所以则回到了上一层的递归，刚刚的head变成了head.next。

学新通

这个时候进行判断，head.val == head.next.val 所以return head.next 把head删除了，只留下一个重复的元素。

学新通

然后继续进行判断，head.val != head.next.val，所以head.next和head都保留了，return head。

学新通

保留之后链表是这样的形态，然后继续进行递归。

public ListNode deleteDuplicates(ListNode head) {
// 1.base case
if (head == null || head.next == null) {
return head;
}
head.next = deleteDuplicates(head.next);
return head.val == head.next.val ? head.next : head;
}

二、删除所有重复数字结点，只留下不同数字

给定一个已排序的链表的头 head ，删除原始链表中所有重复数字的节点，只留下不同的数字。返回已排序的链表。

学新通

2.1带头链表解法

这种情况下不能使用单链表解法了，会更加困难，因为可能头结点也需要被删除，所以需要制造一个前驱结点，来判断前驱结点后面的结点需不需要被删除。

同样的我们要排除链表为空和头结点的后继节点为空的情况，以上两种情况可以直接返回head。

然后也是要创建一个带头链表dummyHead，使他的第一个数为-101，然后让dummyHead.next = head，使自己创建的带头链表和给的单链表做出联系。

但是这时我们需要使prev= dummyHead，不能让他为dummyHead.next，为了防止头结点也是重复元素而不被删除。

重复元素都必须被删除的情况下，我们需要比较两个元素的话，就需要创建两个变量cur和sec。使cur = prev.next（也就是让cur表示原链表的头结点），sec = cur.next。

学新通

当cur和sec不相等的时候，证明cur在这个链表中没有重复元素（因为这个链表是有序的，后面都只会和他相同或者比他大，出现一个比他大的后面都比他大）那么prev就可以向后移动一位，然后cur和sec都跟着移动一位以及判断。（此处忽略cur移动到2，直接将cur移动到第一个3，sec移动到第二个3，来进行重复元素的操作）

学新通

现在sec.val == cur.val，所以我们我们不能动prev和cur，需要将sec继续向后移动，接着判断所以我们要使用while循环，并且循环的终止条件就是sec==null，因为sec总是先移动当他为空的时候没有具体值了循环就结束了，或者是sec.val != cur.val的时候进行下一步判断。

学新通

当循环结束后，sec和cur不再是重复的元素，但是也不能保证呢过sec和后面的不会重复所以prev还是不能动，但是prev的后继结点可以变为sec，这种情况下就已经删除掉中间重复的元素了。然后cur也变为sec，sec变为cur的后继结点，继续接下来的判断。

学新通

这个时候cur和sec又相等了所以重复进行上述操作。

学新通

这个时候sec==null了，所以整个链表中已经不存在重复元素了，所以结束循环，直接返回dummyHead.next就能得到修改后的链表了。

public ListNode deleteDuplicates(ListNode head) {
if(head == null||head.next== null){
return head;
}
ListNode dummyHead = new ListNode(-101);
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode cur = prev.next;
while(cur!= null){
ListNode sec = cur.next;
if(sec == null){
break;
}
if(cur.val!= sec.val){
prev = prev.next;
}else {
while (sec!=null&&sec.val == cur.val){
sec = sec.next;
}
prev.next = sec;
}
cur = sec;
}
return dummyHead.next;
}

2.2 递归方法

然后就要判断当前头节点和第二个节点是否相等的问题，如果head.val != head.next.val，那么头结点不是要删除的节点则直接处理子节点的删除，head.next = deleteDuplicates(head.next)，然后返回head。

如果头节点就是待删除的节点，就需要先把头节点处理完毕，就用到一个变量newHead使他等于head.next，然后进行while循环，判断newHead != null && newHead.val == head.val，只有在这种情况下newHead需要继续向后移，直到while循环走出则newHead是第一个不和head值相等的结点，那么前面的结点都需要删除，所以return deleteDuplicates(newHead)。继续进行递归。

刚开始进行递归的时候是如下图的，head和newHead的值不相等，所以进入deleteDuplicates(head.next)，不删除head。

学新通