链表：单链 / 双链 / 环形

// 运行环境：Node.js 14+
// 保存为 dsa-l5.js，执行：node dsa-l5.js

class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next }
}

// 遍历
function traverse(head) {
  let cur = head
  while (cur) { console.log(cur.val); cur = cur.next }
}

// 插入：先接后断（顺序不能反！）
function insertAfter(prev, node) {
  node.next = prev.next
  prev.next = node
}

// 删除：跳过目标
function deleteNext(prev) { if (prev.next) prev.next = prev.next.next }

function removeValue(head, val) {
  const dummy = new ListNode(0, head) // 虚拟头，永远不动
  let cur = dummy
  while (cur.next) {
    if (cur.next.val === val) cur.next = cur.next.next // 跳过
    else cur = cur.next
  }
  return dummy.next // 真实新头
}

function reverse(head) {            // 迭代：三指针 prev/cur/next
  let prev = null, cur = head
  while (cur) {
    const next = cur.next
    cur.next = prev
    prev = cur
    cur = next
  }
  return prev
}
function reverseR(head) {           // 递归：子链反转后让原头指向新尾
  if (!head || !head.next) return head
  const newHead = reverseR(head.next)
  head.next.next = head
  head.next = null
  return newHead
}

function hasCycle(head) {
  let slow = head, fast = head
  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}

function mergeTwo(l1, l2) {
  if (!l1) return l2
  if (!l2) return l1
  if (l1.val < l2.val) { l1.next = mergeTwo(l1.next, l2); return l1 }
  l2.next = mergeTwo(l1, l2.next); return l2
}
// 调用示例
const h = new ListNode(1, new ListNode(2, new ListNode(3)))
console.log(reverse(h).val) // 3（反转后头是 3）