JZ76 删除链表中重复的结点

JZ76 删除链表中重复的结点

描述

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

数据范围：链表长度满足 0 \le n \le 1000 \0≤n≤1000 ，链表中的值满足 1 \le val \le 1000 \1≤val≤1000

进阶：空间复杂度 O(n)*O*(n) ，时间复杂度 O(n) *O*(n)

例如输入{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. 建一个「虚拟头节点」newHead 以减少边界判断，往后的答案链表会接在 newHead 后面；
2. 使用 tmp 代表当前有效链表的结尾；
3. cur指向pHead，cur 指针进行链表扫描。

对原链表进行遍历，只要原链表尚未到达结尾，我们就重复如下决策（保留/跳过逻辑）：

• 保留：cur 已经没有下一个节点，cur 可以被保留（插入到答案结尾指针 tmp 后面）；cur 有一下个节点，但是值与 cur 不相同，cur 可以被保留；
• 跳过：当发现 cur 与下一个节点值相同，需要对「连续相同一段」进行跳过。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        //新建虚拟节点
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        ListNode cur = pHead;

        while(cur != null){
            if(cur.next != null && cur.val == cur.next.val){
                while(cur.next != null && cur.val == cur.next.val){
                    cur = cur.next;//不是最后一个节点重复
                }
                cur = cur.next;//最后一个节点重复，cur 往后后走，删除最后一个节点，此时cur == null 跳出循环
            }else{//没有重复节点，尾插
                tmp.next = cur;
                tmp = tmp.next;
                cur = cur.next;
            }
        }

        //防止当最后一个节点重复时，要记得将tmp.next置为空
        tmp.next = null;
        return newHead.next;
    }
}