本文共 1653 字，大约阅读时间需要 5 分钟。

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

分析

从头遍历整个链表，如果当前的节点（pNode）与下一个节点的值相同，则都是重复的节点，可以进行删除。为了保证删除之后的链表中间不断开，需要保存当前节点的前一个节点pPreNode，将其与后面第一个不重复的节点相连。注意，当头结点是重复节点的时候，头结点也会被删除。

牛客AC：

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {
       public ListNode deleteDuplication(ListNode pHead) {        if(pHead == null)            return null;        if(pHead.next == null)  // 只有一个头结点            return pHead;        ListNode pNewHead = pHead;      // 返回链表中新的头结点，注意头结点可能也会因重复删除        ListNode pPreNode = null;       // 保存遍历当前节点的前一个节点        ListNode pNode = pHead;         // 当前节点        while(pNode != null) {            ListNode pNext = pNode.next;    // 当前节点的后一个节点，判断是否重复            // 后一个节点不为空，值相等，则重复            if(pNext != null && pNode.val == pNext.val) {                   // 先记录下需要被删除的节点及其值                int val = pNode.val;                ListNode pToBeDel = pNode;                // 遍历后面的，找到pNext是一个不再重复的节点为止                while(pToBeDel != null && pToBeDel.val == val) {                    pNext = pToBeDel.next;                    pToBeDel = pNext;                }                if(pPreNode == null)    // 更新头结点                    pNewHead = pNext;                else                    pPreNode.next = pNext;  // 修改链表，将pre直接连接到next，则中间的重复节点全部被删除                pNode = pNext;            } else {        // 否则，往后继续遍历                pPreNode = pNode;                pNode = pNode.next;            }        }        return pNewHead;    // 返回新的头结点    }}

参考

转载地址：http://ikxgi.baihongyu.com/