Heading

82.删除排序链表中的重复元素-ii (opens new window)

Tags: algorithms linked-list

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Medium (49.74%)
• Likes: 410
• Dislikes: -
• Total Accepted: 76.4K
• Total Submissions: 153.3K
• Testcase Example: '[1,2,3,3,4,4,5]'

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

/*
 * @lc app=leetcode.cn id=82 lang=javascript
 *
 * [82] 删除排序链表中的重复元素 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */


 function ListNode(val) {
     this.val = val;
     this.next = null;
 }

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    const hair = new ListNode();
    hair.next = head;
    let p = hair, q = p.next, tmpVal = q ? q.val : null;
    while (q && q.next) {
        if (tmpVal === q.next.val) {
            //删除相同元素的节点
            while(q && q.next && tmpVal === q.next.val){
                q = q.next
            }
            q = q.next
            p.next = q
            tmpVal = q ? q.val : null;
        } else {
            //更新p、q和当前值
            p = q
            q = q.next
            tmpVal = q ? q.val : null;
        }
    }
    return hair.next;
};

//方法二：hash记录元素的出现次数
//方法三：尾插法新建链表
// @lc code=end


// @after-stub-for-debug-begin
module.exports = deleteDuplicates;
// @after-stub-for-debug-end