关于java:牛客网高频算法题系列BM15删除有序链表中重复的元素I

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

题目形容

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

原题目见：BM15 删除有序链表中反复的元素-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$
置信保持的力量！