链表

链表

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指向另一个节点的指针（在 JavaScript 中是引用）。链表的起点叫做头节点（head），链表的终点叫做尾节点（tail），尾节点的指针指向null。

在 JavaScript 中，链表通常可以通过构造函数或类来实现节点

class ListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
const listNode = new ListNode(1)

链表的优点包括动态大小和有效的元素插入与删除。其缺点是不支持快速随机访问，且需要额外的存储空间来存储指针。

链表的遍历

let cur = head
while (cur) {
  console.log(cur.data)
  cur = cur.next
}

翻转链表

原地翻转

利用两个变量缓存前后节点，原地翻转链表

const reverseListNodes = (head) => { 
  let pre = null
  let next = null
  
  // 当前遍历的节点，从头开始
  let cur = head
  while (cur !== null) {
    // 因为一会儿要修改 cur 节点的 next，因此要想循环继续，需要将 next 缓存一下
    next = cur.next
    
    // 改变当前节点的 next 指向
    cur.next = pre
    
    // 准备下次遍历的数据
    pre = cur
    // cur = cur.next 继续遍历
    cur = next
  }

  // 此时 pre 就是新的 head
  return pre
}

利用栈

栈就是把左侧堵住的数组，只能用 pop 和 push 方法

两次遍历，第一次遍历用于将各个节点依次压入栈中，第二次遍历用于重新链接节点

const reverseListNodes = (head) => {
  const stack = []
  // 遍历整个链表，将各个节点依次压入栈中
  let cur = head
  while (cur !== null) {
    stack.push(cur)
    cur = cur.next
  }

  // 初始化新头结点
  const resultHead = stack.pop() || null
  
  // 从栈中弹出所有元素，并依次重新链接它们
  let _cur = resultHead
  while (_cur) {
    // 每次循环改变 _cur 的 next 指向为 pop 出来的节点
    _cur.next = stack.pop() || null
    // 更新 _cur 为 _cur.next 节点，以继续遍历
    _cur = _cur.next
  }

  return resultHead
}

链表排序

思路同上，借鉴数组

function sortList(head: ListNode | null): ListNode | null {
    if(!head) return null
    const arr = []
    while(head){
        arr.push(head)
        head = head.next
    }
    arr.sort((a,b) => a.val - b.val)
    let result = arr.shift() || null
    let cur = result
    while(cur) {
        cur.next = arr.shift() || null
        cur = cur.next
    }
    return result
};

环检测

快慢指针，以 fast 为准，当 fast 到头了就返回 false；否则 slow 走一步，fast 走两步，当 fast === slow 时返回 true

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

合并有序链表

初始结果头节点 -1，while 同时遍历两个链表，谁小就接上谁，然后小的往前走一步。最后拼上剩下的部分，返回 result.next

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let result = new ListNode(-1)

    let cur = result;
    while(list1 && list2) {
        if(list1.val >= list2.val) {
            cur.next = list2
            list2 = list2.next
        }else {
            cur.next = list1
            list1 = list1.next
        }
        cur = cur.next
    }
    cur.next = list1 || list2

    return result.next
};

链表相交

先遍历 A，再遍历 B。用 Set 收集

function getIntersectionNode(headA, headB) {
    const set = new Set()
    while(headA) {
        set.add(headA)
        headA = headA.next
    }
    while(headB) {
        if(set.has(headB)){
            return headB
        }
        headB = headB.next
    }
    return null
};

回文链表

利用数组， reverse 之后跟之前一样就是回文

删除链表的倒数第 n 个节点

删除节点

list.next = list.next.next;

两次遍历，第一次统计长度，第二次比较 n 和 长度，每次遍历 length --，直到 n === length，说明此时 cur 已经遍历到了这个位置，删除即可

注意初始化的和返回的节点

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const result = new ListNode(-1, head)
    let length = 0, cur = head
    while(cur) {
        length ++
        cur = cur.next
    }
    // 开始第二次遍历
    cur = result
    while(n !== length) {
        cur = cur.next
        length --
    }
    cur.next = cur.next.next
    return result.next
};

两数之和

初始化结果 ListNode(0) 、指针 curPoint 和进位 0

遍历两个链表，取数加和，更新进位：Math.floor(sum/10)，更新节点：new ListNode(sum % 10)，更新指针，继续遍历。最后返回 dummy.next

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(0)
    let curPoint = dummy
    let carry = 0
    // 考虑到最后一位加完存在进位的情况，所以循环条件要有 carry
    while(l1 || l2 || carry) {
        const x = l1?.val || 0
        const y = l2?.val || 0
        const sum = x + y + carry
        carry = Math.floor(sum / 10)
        curPoint.next = new ListNode(sum % 10)
        curPoint = curPoint.next
        if(l1) l1 = l1.next
        if(l2) l2 = l2.next
    }
    return dummy.next
};