LeetCode83. 删除排序链表中的重复元素:迭代+递归解法

题意

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

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

题解

迭代方法

由于链表是升序的，所以重复的元素一定相邻着出现，那么判断是否重复，只需要通过比较当前节点是否和上一个节点值相同即可，若相同，则让上一个节点的next指向当前节点的next，来删除当前重复元素；若不相同则无需删除，继续向后迭代。

//迭代方法
class Solution {
          
   
    public ListNode deleteDuplicates(ListNode head) {
          
   
        if(head==null)return null;
        ListNode pre=head,cur=pre.next;
        while(cur!=null){
          
   
            if(pre.val==cur.val)//说明重复
                pre.next=cur.next;
            else
                pre=cur;
            cur=cur.next;
        }
        return head;
    }
}

递归方法

递归方法也很简单，deleteDuplicates方法可以处理当前链表，使得其没有重复元素，那我们可以在deleteDuplicates方法中通过自身来处理子链，然后判断链表头节点是否和子链重复，不重复则，让头节点连接子链，然后返回头节点；若重复则直接返回子链头节点。再考虑边界，不论什么样的链表我们都先处理它的子链，那不断的处理子链，直到子链为空，此时为空的子链去重后还是空，所以我们返回空值就好。

class Solution {
          
   
   public ListNode deleteDuplicates(ListNode head) {
          
   
        if(head==null)return null;
        head.next=deleteDuplicates(head.next);
        if(head.next==null)return head;
        return head.val!=head.next.val?head:head.next;
    }
}