算法训练营第4天｜24.两两交换链表节点、19.删除链表的倒数第N个节点、160.链表相交、142.环形链表II

//  指针法
var swapPairs = function(head) {
  // 定义虚拟节点，主要是为了统一后续的节点循环条件统一
  let node = new ListNode(0, head)
  // 定义指针指向虚拟节点
  let cur = node
  // 如果是奇数链表，1,2,3,4,5，当 cur = 4的时候，剩下最后一个 5 可以不用操作，也就是说 cur.next.next 为空就终止，对应循环条件就是 while(cur.next && cur.next.next !== null)
  // 如果是偶数链表，1,2,3,4，当 cur = 4时，后续也不用操作，也就是说cur.next为空就终止，对应循环条件就是 while(cur.next !== null)
  // 所以循环终止的条件就是cur.next（偶数）为空，或者cur.next.next（奇数）为空，就不用操作了
  // 但因为奇数的终止条件其实已经包含偶数的终止条件，如果想两个都满足，那么只需要用奇数的循环终止条件就行
  while (cur.next && cur.next.next !== null) {
    // 节点 1
    let temp = cur.next
    // 节点 3
    let temp1 = cur.next.next.next
    // node - 节点 2
    cur.next = cur.next.next
    // 节点 2 - 节点 1
    cur.next.next = temp
    // 节点 1 - 节点 3
    temp.next = temp1
    // 移动指针
    cur = cur.next.next
  }
  return node.next
};

// 递归法
var swapPairs = function(head) {
  let node = new ListNode(0, head)
  function tempfun(cur) {
    // 递归终止条件
    if (cur.next === null || cur.next.next === null) return node.next
    // 保存节点 1,3
    let temp = cur.next
    let temp1 = cur.next.next.next
    // cur -> 2
    cur.next = cur.next.next
    // 2 -> 1
    cur.next.next = temp
    // 1 -> 3
    temp.next = temp1
    return tempfun(cur.next.next)
  }

//  暴力解法，先统计长度再找到目标节点
var removeNthFromEnd = function(head, n) {
  let node = new ListNode(0, head)
  let cur = node
  let size = 0
  // 先统计长度
  while (cur) {
    size ++
    cur = cur.next
  }
  // 找到目标节点的 index
  i = size - n
  let pre = node
  let cur1 = node.next
  while (i>=0) {
    i--
    if (i=== 0) {
      // 找到目标节点就进行删除
      pre.next = cur1.next
      // 返回目标节点
      return node.next
    }
    pre = cur1
    cur1 = cur1.next
  }
};

// 双指针，快慢指针解法
var removeNthFromEnd = function(head, n) {
  // 双指针
  let node = new ListNode(0, head)
  let fast = node
  let slow = node
  let i = 0
  while (fast) {
    // 快指针的 next 为空，说明走到了头
    if (fast.next === null) {
      // 就删除慢指针的下一个节点
      slow.next = slow.next.next
      // 返回头节点
      return node.next
    } else {
      i++
      fast = fast.next
      // 让快指针先走，走到＞n 的时候，再让慢指针走
      if (i>n) {
        slow = slow.next
      }
    }
  }
};

// 遍历链表，获取链表长度
const getLength = function (head) {
  let len = 0
  let cur = head
  while (cur) {
    len ++
    cur = cur.next
  }
  return len
}

var getIntersectionNode = function(headA, headB) {

  let curA = headA
  let curB = headB
  let lenA = getLength(headA)
  let lenB = getLength(headB)
  if (lenA < lenB) {
    // 保证长的在上面
    [curA, curB] = [curB, curA];
    [lenA, lenB] = [lenB, lenA]
  }
  // 对齐两个链表的指针，找出差值，让长链表指针先走
  let i = lenA - lenB
  while (i > 0) {
    i--
    curA = curA.next
  }
  // 这个时候就一起走指针，后续的长度都相同，所以无论是判断curA还是curB，返回curA或者curB 都行
  while (curA) {
    // 如果指针相同，则返回任意一个指针
    if (curA === curB) {
      return curA
    }
    curA = curA.next
    curB = curB.next
  }

};

var detectCycle = function(head) {
  let slow = head
  let fast = head
  while(fast && fast.next) {
    // 快指针 2 步走
    fast = fast.next.next
    // 慢指针 1 步走
    slow = slow.next
    // 当快慢指针相遇时
    if(slow === fast) {
      // 当 n = 1 时 x 的距离和 z 的距离相等
      // 所以 x 和 z 相遇时的节点就是环的入口
      let x = head
      let z = fast
      while(x !== z) {
        x = x.next
        z = z.next
      }
      return x
    }
  }
  // 没找到就返回 null
  return null
};