快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如 fast 每次增长两个，slow 每次增长一个。

示例

字符串压缩

function compressString(S){
let newS = ''

let slow = 0
let fast = 0

// 1.循环条件
while(fast < S.length -1){
  // 3.快慢比较
  if(S[slow]!==S[fast+1]){
    // 记录
    newS += S[slow]+(fast-slow+1)
    slow = fast+1
  }
  // 2.递增
  fast++
}
// 4.记录最后一个
newS += S[slow]+(fast-slow+1)

// 5.判断字符串长度是否压缩
if(newS.length < S.length){ // 压缩
  return newS
}else{ // 不压缩
  return S
}
}

var str = 'aabcccccaaa'
console.log(compressString(str))
//a2b1c5a3

移除链表中重复节点

思路：快慢指针 + Set

const head = {
'val':1,
'next':{
    'val':2,
    'next':{
        'val':3,
        'next':{
            'val':3,
            'next':{
                'val':2,
                'next':undefined
            }
        }
    }
}
}

var removeDuplicateNodes = function(head) {
let set = new Set()

// 拷贝
let slow = head
let fast = head

while(fast){
  if(!set.has(fast.val)){// 不存在
    set.add(fast.val)
    // 慢指针记录
    slow = fast
  }else{  // 存在
    // 慢指针干预：向前跳一位
    slow.next = fast.next // 此时可以对原数据进行改变？？
  }

  fast = fast.next
}

return head
};

console.log(removeDuplicateNodes(head))