算法:删除链表中重复的结点

删除链表中重复的结点

删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

分析

构建一个哨兵节点scott;

然后建立cur节点和curNext节点, 每次判断curNext是否与后面的相同, 进行跳过节点

代码

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null || pHead.next == null) return pHead;

        ListNode scott = new ListNode(0);
        scott.next = pHead;

        ListNode cur = scott, curNext = pHead;

        while (curNext != null) {
            // 出现重复
            // cur.next.val == cur.next.next.val
            if (curNext.next != null && curNext.val == curNext.next.val) {
                // 跳过操作
                while (curNext.next != null && curNext.val == curNext.next.val) {
                    curNext = curNext.next;
                }
                // 添加不重复元素
                cur.next = curNext.next;
                curNext = curNext.next;
            } else {
                // 不重复
                cur = cur.next;
                curNext = curNext.next;
            }
        }
        return scott.next;
    }
}