牛客网高频算法题系列-BM15-删除有序链表中重复的元素-I题目描述

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次

原题目见：删除有序链表中重复的元素-I_牛客题霸_牛客网

解法一：链表遍历

首先，考虑特殊情况，如果链表为空或者只有一个结点，不会有重复的元素，返回原链表。

否则，遍历链表结点，判断是否有重复的元素，处理过程如下：

使用pre记录上一个未重复的结点，初始化为链表头；

然后从链表的第二个结点next开始遍历链表结点；

如果next和pre的值相同，则删除当前重复结点；

如果next和pre的值不相同，则更新pre的值。

遍历完成后，链表的头结点并没有变化，返回头结点即可。

代码

public class Bm015 {    /**     * 删除有序链表中重复的元素-I     *     * @param head ListNode类     * @return ListNode类     */    public static ListNode deleteDuplicates(ListNode head) {        // 如果链表为空或者只有一个结点，不会有重复的元素，返回原链表        if (head == null || head.next == null) {            return head;        }        // pre记录上一个未重复的结点        // next为从第二个节点开始判断是否有重复元素        ListNode pre = head, next = head.next;        // 遍历链表        while (next != null) {            // 如果当前结点的值和pre的值相同，则要删掉当前结点，修改pre的next指针即可            if (pre.val == next.val) {                pre.next = next.next;            } else {                // 如果当前结点未重复，则更新pre                pre = next;            }            next = next.next;        }        return head;    }    public static void main(String[] args) {        ListNode head = ListNode.testCase6();        System.out.println("原链表为");        ListNode.print(head);        System.out.println("删除有序链表中重复的元素后的链表为");        ListNode.print(deleteDuplicates(head));    }}

1.01^{365} ≈ 37.7834343329 0.99^{365} ≈ 0.02551796445 相信坚持的力量！