删除链表中重复的结点

题目描述

示例

示例1

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

示例2

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

代码

代码1 使用set暴力解法

/*
因为是删除重复的项，所以使用个set
1. 先遍历单链表相邻的元素，如果相等，就加入到set中
2. 遍历完一遍后，再重新遍历一遍开始删除
3. pre指向前一个节点，current指向当前节点
3. 若果current在set中，就pre.next = current.next
4. 否则就不是重复值，pre = pre.next, current= current.next
*/
function deleteDuplication(pHead)
{
    if(!pHead) return null
    
    let set = new Set() // 用来存储重复的值
   
    let dummy = new ListNode(-1) // 虚拟节点
    dummy.next = pHead
    let p1 = dummy
    let p2 = dummy.next
    
    // 第一遍遍历，找相邻重复的值
    while(p2){
        p2 = p2.next
        p1 = p1.next
        // 如果p2不是null，没有到头
        // 且 p1 和 p2 相等
        if(p2!==null && p2.val === p1.val){
            set.add(p2.val) // 把重复的值保存到set中
        }
    }
    
    // 第二遍遍历，删除重复的值
    let pre = dummy
    let current = dummy.next
    
    while(current){
        if(set.has(current.val)){ // 若果在set中发现这个是重复的值，直接删除
            // 直接删除
            current = current.next
            pre.next = current
        }else { // 若果发现不是重复的值，就继续往下走
            current = current.next
            pre = pre.next
        }
    }
    
    return dummy.next
}

代码2 直接删除

/*
1. 查看当前节点是否与下一节点相等
2. 如果相等，就继续往下查找，查找同样值的最大长度，然后改变指针指向，删除节点
*/
function deleteDuplication(pHead)
{
    // write code here
    let dummy = new ListNode(-1) // 虚拟头结点
    dummy.next = pHead
    
    let pre = dummy
    let current = pHead
    
    while(current){
        // 找相邻的两个值是否相等
        if(current.next && current.val === current.next.val){// 当相等时
            current = current.next
            // 当相等时 继续往下找，找到最大长度的相等值，然后改变指针指向
            while(current.next && current.val === current.next.val){
                current = current.next
            }
            // 开始删除
            current = current.next
            pre.next = current
        }else { // 当不相等时
            current = current.next
            pre = pre.next
        }
    }
    
    return dummy.next
}

题目来源

JZ76 删除链表中重复的结点