反转链表、删除链表的倒数第N个节点、合并两个有序链表和两数相加

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

const reverseList = function (head) {
  if (head === null || head.next === null) {
    return head;
  }
  let p = head.next;
  head.next = null; // 旧的头指针是新的尾指针,next需要指向null
  while (p !== null) {
    const temp = p.next; // 先保留下一个step要处理的指针
    p.next = head; // 然后p和head进行反向
    head = p; // 指针后移
    p = temp; // 指针后移
  }
  return head;
};

const reverseList = function (head) {
  if (head === null || head.next === null) {
    return head;
  }
  //这里的cur就是最后一个节点，也就是反转后的头节点
  const newHead = reverseList(head.next); // 反转后的头节点
  //这里请配合动画演示理解
  //如果链表是 1->2->3->4->5，那么此时的cur就是5
  //而head是4，head的下一个是5，下下一个是空
  //所以head.next.next 就是5->4
  head.next.next = head; // 将反转后的链表的尾结点与当前节点相连
  //防止链表循环，需要将head.next设置为空
  head.next = null;
  //每层递归函数都返回cur，也就是最后一个节点
  return newHead;
};

给定一个链表: 1->2->3->4->5, 和 n = 2.
​
当删除了倒数第二个节点后，链表变为 1->2->3->5.

const removeNthFromEnd = (head, n) => {
  let first = head;
  let second = head;
  while (n > 0) {
    first = first.next;
    n -= 1;
  }
  if (!first) return head.next; // 如果first为null，则要删除的节点是首节点，直接返回head的下一个节点
  while (first.next) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return head;
};

const removeNthFromEnd = (head, n) => {
  let cur = head;
  while (cur.next) {
    cur.next.prev = cur;
    cur = cur.next;
  }
  if (n === 1) {
    // 删除最后一个节点
    if (!cur.prev) { // 若是头节点则直接返回null
      return null;
    } else {
      cur.prev.next = null;
      return head;
    }
  }
  while (n > 0 && cur) {
    if (n === 1) {
      if (!cur.prev) {
        // 删除第一个节点
        cur.next.prev = null;
        return cur.next;
      } else {
        cur.prev.next = cur.next;
        cur.next.prev = cur.prev;
        return head;
      }
    }
    cur = cur.prev;
    n -= 1;
  }
};

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

const mergeTwoLists = function (l1, l2) {
  if (l1 === null) {
    return l2;
  }
  if (l2 === null) {
    return l1;
  }
  if (l1.val <= l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
};

const mergeTwoLists = function (l1, l2) {
  const prevHead = new ListNode(-1);
  let prevNode = prevHead;
  while (l1 !== null && l2 !== null) {
    if (l1.val <= l2.val) {
      prevNode.next = l1;
      l1 = l1.next;
    } else {
      prevNode.next = l2;
      l2 = l2.next;
    }
    prevNode = prevNode.next;
  }
  prevNode.next = l1 || l2;
  return prevHead.next;
};

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

/**
 * Definition for singly-linked list.
 */
function ListNode (val) {
  this.val = val;
  this.next = null;
}
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = function (l1, l2) {
  // 两数之和联表
  const sumListNode = new ListNode(0);
  // 指针1 指向 链表1
  let pointer1 = l1;
​
  // 指针2 指向 链表2
  let pointer2 = l2;
​
  // current 指向 两树之和的链表
  let current = sumListNode;
​
  // 逐位相加的进位
  let carry = 0;
​
  // 如果指针 pointer1、pointer2 还未移动结束
  while (pointer1 || pointer2) {
    // 如果 pointer1 已经移动到链表 l1 的末尾，当前值为0
    const num1 = pointer1 ? pointer1.val : 0;
​
    // 如果 pointer1 已经移动到链表 l1 的末尾，当前值为0
    const num2 = pointer2 ? pointer2.val : 0;
​
    // sum为当前移动位的两数之和
    const sum = carry + num1 + num2;
​
    // 存储进位
    carry = Math.floor(sum / 10);
​
    // sumListNode添加一个当前 l1 和 l2 相加的node ，值为 sum的个位数
    current.next = new ListNode(sum % 10);
​
    // current 指针后移一位
    current = current.next;
​
    // 如果 pointer1 未移动到 l1 的结尾，继续后移一位
    if (pointer1) {
      pointer1 = pointer1.next;
    }
     // 如果 pointer2 未移动到 l2 的结尾，继续后移一位
    if (pointer2) {
      pointer2 = pointer2.next;
    }
  }
  // 如果有进位，两数之和的联表，加一个进位的 node
  if (carry > 0) {
    current.next = new ListNode(carry);
  }
​
  return sumListNode.next;
};

/**
 * Definition for singly-linked list.
 */
function ListNode (val) {
  this.val = val;
  this.next = null;
}
/**
 * @description 将链表转换为数字
 * @param {ListNode} listNode
 * @return {BigInt}
 */
const listNodeToNum = function (listNode) {
  let numString = '';
  let currentNode = listNode;
  while (currentNode) {
    numString = currentNode.val + numString;
    currentNode = currentNode.next;
  }
  // eslint-disable-next-line no-undef
  return BigInt(numString);
};
​
/**
 * @description 数字转为链表
 * @param {number} num 数字
 * @return {ListNode}
 */
const numToListNode = function (num) {
  let listNode = null;
  const numString = num.toString();
  for (let i = 0; i < numString.length; i++) {
    const newNode = new ListNode(numString[i]);
    newNode.next = listNode;
    listNode = newNode;
  }
  return listNode;
};
​
const addTwoNumbers = function (l1, l2) {
  return numToListNode(listNodeToNum(l1) + listNodeToNum(l2));
};