前言

今天，小编来分享一道热门的面试算法题——删除有序链表中重复的元素。

问题描述

给出一个升序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

例如：

给出的链表为1 -> 2 -> 3 ->3 -> 4 -> 4 -> 5，返回1-> 2 -> 5.

示例

示例1

输入：{1,2,3}

返回值：{1}

示例2

输入：{}

返回值：{}

思路

  1. 给链表加上表头，因为可能会出现第一个节点就需要删除
  2. 遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。
  3. 在第2步中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
  4. 返回时去掉添加的表头。

注意：

  • 这道题删除的是所有重复的元素，也就是说凡是有重复出现的任何数就全部删除，并不是删除至只留下一个。
  • 外层循环的条件cur.next != null && cur.next.next != null
  • 内层循环的条件cur.next != null && cur.next.val == temp，其实内层循环条件很简单，但是一定要细心，小编第一次遇到这道题的时候就在这入了坑

代码实现

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        //空链表
        if(head == null) 
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head; 
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){ 
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){ 
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp) 
                    cur.next = cur.next.next;
            }
            else 
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next; 
    }
}