JZ76: 删除链表中重复的结点

[songyy5517]

描述 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5。 例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

示例1

输入：{1,2,3,3,4,4,5}
返回值：{1,2,5}

示例2

输入：{1,1,1,8}
返回值：{8}

分析 这道题本质上是考察对链表的操作。题中的关键信息是链表中节点是排序的，因此重复的节点必然都挨在一起。从而整个问题可大致分为两部分：1. 识别重复节点（遍历链表，比较当前节点跟下一个节点）； 2. 删除重复节点（双指针）。

[songyy5517]

思路：双指针

1. 异常处理；
2. 定义双指针和伪头节点head_；
   • p1：检查重复节点；
   • p2：指向p1的上一个节点，初始化成伪头节点；
3. 遍历链表： （1）比较p1和其下一个节点，判断是否重复；若重复，则向后移动p1，直到与下一个节点不同，然后删除重复节点。 （2）若没重复，则同时向后移动p1和p2。
4. 返回伪头节点的下一个节点。

复杂度分析

• 时间复杂度： $O(N)$ ，遍历整个链表中的节点，使用 $O(N)$ 大小的时间；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量。

[songyy5517]

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        // 思路：双指针。
        // 1. 异常处理
        if (pHead == null)
            return null;

        // 2. 定义双指针
        ListNode p1 = pHead;    // 检验重复节点
        ListNode head_ = new ListNode(0);    // 伪头节点
        head_.next = p1;
        ListNode p2 = head_;    // 指向最后一个不重复节点

        while (p1 != null){
            // 出现重复节点
            if (p1.next != null && p1.val == p1.next.val){
                while (p1.next != null && p1.val == p1.next.val)
                    p1 = p1.next;

                // 删除重复节点
                p2.next = p1.next;
            }

            // 没遇到重复节点，指针继续向后移动
            else 
                p2 = p1;

            p1 = p1.next;
        }

        return head_.next;
    }
}

[songyy5517]

2024/5/3