leetcode-LinkedList

一、模板

1. 递归（从后往前处理）

var problem = (root)=>{
  return rec(root,null)
  
  function rec(cur,prev){
    if(cur === null){
      // 1. terminator
      return prev
    }
    // 2. drill down
    let ret = dfs(cur.next,cur)
    
    // 3. process cur
    cur.prev = prev
    
    // 4. reverse
    return ret
  }
}

2. 非递归（从前往后处理）

var problem = (root)=>{
  let prev = null, cur = root
  while(cur !== null){
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
}

3. 是否有环

• 哈希
• 快慢指针

二、题目

237. 删除链表中的节点

var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

206. 反转链表/剑指 Offer 24. 反转链表

/**
 * 递归
 */

var reverseList = function(head) {
  return dfs(head,null)

  function dfs(cur,prev){
    if(cur === null) return prev

    const ret = dfs(cur.next, cur)
    cur.next = prev
    return ret
  }
};

/**
 * 非递归
 */

var reverseList = function(head) {
  let cur = head, prev = null
  while(cur !== null){
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
};

203. 移除链表元素

/**
 * 递归
 */

var removeElements = function (head, val) {
  if(head === null) return null
  head.next = removeElements(head.next,val)
  return head.val === val ? head.next : head
};

/**
 * 不带虚拟头节点先序
 */

var removeElements = function (head, val) {
  while (head !== null && head.val === val) {
    const delNode = head
    head = head.next
    delNode.next = null
  }

  if (head === null) return null

  let prev = head
  while (prev.next !== null) {
    if (prev.next.val === val) {
      const delNode = prev.next
      prev.next = delNode.next
      delNode.next = null
    } else {
      prev = prev.next
    }
  }
  return head
};

/**
 * 带虚拟头节点先序
 */

var removeElements = function (head, val) {
 const dummyHead = new ListNode(-1)
  dummyHead.next = head

  let prev = dummyHead
  while (prev.next !== null) {
    if (prev.next.val === val) {
      prev.next = prev.next.next
    } else {
      prev = prev.next
    }
  }
  return dummyHead.next
};

21. 合并两个有序链表

// 归并
var mergeTwoLists = function (l1, l2) {
  let dummyHead = new ListNode()
  let prev = dummyHead
  let i = l1
  let j = l2
  while (i && j) {
    if (i.val <= j.val) {
      prev.next = i
      i = i.next
    } else {
      prev.next = j
      j = j.next
    }
    prev = prev.next
  }

  if (i) { prev.next = i }
  if (j) { prev.next = j }

  return dummyHead.next
};

24. 两两交换链表中的节点

/**
 * 递归
 */

var swapPairs = function(head) {
    if(head === null || head.next === null) 
      return head

    let nextNode = head.next
    head.next = swapPairs(nextNode.next)
    nextNode.next = head
    return nextNode
};

/**
 * 非递归
 */

var swapPairs = function(head) {
    const dummyHead = new ListNode()
    dummyHead.next = head
    let prev = dummyHead
    while(prev.next !== null && prev.next.next !== null){
      let start = prev.next
      let end = prev.next.next
      prev.next = end
      start.next = end.next
      end.next = start
      prev = start
    }
    return dummyHead.next
};

141. 环形链表

/**
 * 快慢指针
 */

var hasCycle = function (head) {
  if(head === null || head.next === null) return false
  let slow = head
  let fast = head.next
  while(slow !== fast){
    if(fast === null || fast.next === null)
      return false
    slow = slow.next
    fast = fast.next.next
  }  
  return true
};

/**
 * 哈希
 */

var hasCycle = function (head) {
  let set = new Set()
  while (head !== null) {
    if(set.has(head))
      return true
    set.add(head)
    head = head.next
  }
  return false
};

19. 删除链表的倒数第N个节点

/**
 * 双指针
 */

var removeNthFromEnd = function(head, n) {
    const dummyHead = new ListNode(0)
    dummyHead.next = head
    let p = dummyHead
    let q = dummyHead
    for(let i = 0;i<=n;i++) 
      q = q.next
    while(q !== null){
      q = q.next
      p = p.next
    }
    let delNode = p.next
    p.next = delNode.next
    delNode.next = null
    return dummyHead.next
};

2. 两数相加

var addTwoNumbers = function(l1, l2) {
    const dummyHead = new ListNode(0)
    let p1 = l1,
        p2 = l2,
        p3 = dummyHead,
        carry = 0

    while(p1 || p2){
      const val1 = p1 ? p1.val : 0
      const val2 = p2 ? p2.val : 0
      const val = val1 + val2 + carry
      p3.next = new ListNode(val % 10)
      
      carry = ~~(val / 10)
      if(p1) p1 = p1.next
      if(p2) p2 = p2.next
      p3 = p3.next
    }
  
    if(carry) p3.next = new ListNode(carry)

    return dummyHead.next
};

83. 删除排序链表中的重复元素

var deleteDuplicates = function(head) {
  let p = head
  while(p && p.next){
    if(p.val === p.next.val){
      p.next = p.next.next
    }else{
      p = p.next
    }
  }
  return head
};