单链表解题思维VS leetcode 最常见的相关题型

1.概念

链表由一组由指针连接的分散节点组成。每个节点包含当前节点和任何后续指针的内容。与数组相比，它不受存储空间的限制，可以更快地执行插入和删除操作。主要有以下几种：

1。单链表

指针指向下一个节点，端点为null

2。双链表

指针指向上一个和下一个节点

3。循环链表

最后一个节点指向第一个节点

解决链表如果遇到问题，先做三步，然后写代码

• 定义链表为解决问题
• 画个图来理清思路
• 定义边界条件

与数组不同，JS官方并没有提供。 a

const head = {
  data: 1,
  next: {
    data: 2,
    next: null,
  },
};

2.leetcode最常见的相关题型

1.合并两个已排序的链表

将两个升序链表合并为一个新的升序链表并返回。新的链表由合并两个指定链表的所有节点组成。

示例:
  输入: l1 = [1,2,4], l2 = [1,3,4]
  输出: [1,1,2,3,4,4]

步骤：

• 解决问题的链表类型是唯一链表
• 想法：
• 想法：和l2增加按顺序，所以l1.val和和和组合是列表中的最小值l2.val❝。 依次重复大小节点的比较，直到l1 l2 的所有条件都null重复为链接列表： null 停止并 下一个 指向另一个链表

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

2. 环链表

如果给定一个链表，判断链表中是否存在环。如果链表中存在一个节点，连续跟随next指针可以再次到达，则链表存在环路。如果链表中有环则返回 true，否则返回 false。为了解决这个问题，必须使用内存O(1)

pos表示如果♼❀pos为，链表末尾加入链表的位置 -1 那么链表中就没有循环了

示例：
  输入：head = [3,2,0,-4], pos = 1 
  输出：true  // 链表中有一个环，其尾部连接到第二个节点

步骤：

• 要解决这个问题，链表类型 a ❙ Tortle and Hare 算法：使用快慢双指针，快指针走两步，慢指针走一步
• 如果链表中有环，那么两个速度不同的指针一定会相遇。从交汇点与链表头节点向下移动，在循环起点相遇

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

3，反向链表

给出单链表的头节点♼

var isPalindrome = function (head) {
  const res = []
  while (head) {
    res.push(head.val);
    head = head.next
  }
  let pre = 0;
  let last = res.length - 1;
  while (pre < last) {
    if (res[pre] !== res[last]) return false;
    pre++;
    last--;
  }
  return true
}

，请使用迭代或递归来反转链表，返回反转链表

示例:
  输入: head = [1,2,3,4,5]
  输出: [5,4,3,2,1]

步骤：

• 解决问题的链表类型：♸迭代思路
  • 将单链表中每个节点的后代指针指向前一个节点。但是

var reverseList = function(head) {
    if(!head || !head.next) return head;
    let prev = null;
    let cur = head;
    while(cur) {
        const curNext = cur.next;
        // 反转后赋值给prev指针
        cur.next = prev;
        prev = cur;
        // 链接到下一个节点
        cur = curNext;
    }
    return prev
};

4。链表的中间节点

给定一个非空的单向链表，以头节点为头节点，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点（ number 给定链表中的节点数在 1 到 100 之间）

示例:
  输入: [1,2,3,4,5]
  输出:  3
  输入: [1,2,3,4,5,6]
  输出:  4

步骤：

• 用于解决此问题的链表类型是唯一链表。 p1 的慢指针的两倍，因此当 p2 到达链表末尾时，p1 正好走了一半并指向链表的中点。
• 同下题

• 边界条件：
  • 如果快指针指向空，则慢指针正好在中间位置

var middleNode = function(head) {
    if(!head || !head.next) return head;
    let slow = head;
    let fast = head;
    while(fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow
};

❝。删除链表底部第n个节点

给定一个链表，删除最后一个链表中的第n个节点，并返回链表的头节点

示例：
  输入：head = [1,2,3,4,5], n = 2
  输出：[1,2,3,5]

步骤：

• 链表类型解决问题唯一链表
• 思路：
  • 使用一次快速指针后，遍历n个节点，两个指针互相返回，直到快速指针指向零。目前慢指针为倒数第n个节点
  • 添加哨兵处理第n个节点
• 边界条件：
  • 当快指针指向慢指针的位置
    • 时，慢指针的指针是从底部开始第n个节点

  const removeNthFromEnd = function (head, n) {
    // 哨兵
    let preHead = new ListNode(0)
    preHead.next = head
    let slow = preHead;
    let fast = preHead;
    // 先走n步
    while (n--) {
      fast = fast.next
    }
    // 一起走
    while (fast && fast.next) {
      fast = fast.next
      slow = slow.next
    }
    slow.next = slow.next.next
    return preHead.next;
  };
  

  6。回文链表

  指定唯一链表的主节点的头。请判断该链表是否为回文相关列表。如果是，则返回true；否则返回 false

  

  示例:
    输入: head = [1,2,2,1]
    输出: true
  

  步骤：

  • 解决这个问题，链表的类型是唯一链表
  • 思路：
    • 使用数组将链表转入数组设置前面而后指针， before 和 after 指针必须相同。如果不同，则不是回文。
    • 如果循环结束不返回false，则为回文。
  • 边界条件：
    • 前后指标不一样。给定两个唯一链表的头节点headA和headB，找到并返回两个单独链表相交的起始节点。问题数据保证整个链结构不存在环路。

      注意：

      • 函数返回结果后，链表必须保持原来的结构（必须复制一个新的链表）
      • 如果两个链表不相交，则返回空值 程序试图满足✜ O(n)时间复杂度，仅使用O(1)内存

      

      示例:
          输入：intersectVal = 4, listA = [1,2,3,4,5], listB = [6,7,4,5], skipA = 3, skipB = 2   // 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 2 个节点
          输出：Intersected at '4'  // 相交节点的值为 4 （注意，如果两个链表相交则不能为 0）
      

      步骤：

      • 解决问题的链表类型是单链表
      • 思路：同上同上，求出链表AB的高度差并消除，交集就已知。以下长度必须相等
      • AB 双指针同时前进。当短链表B的指针遍历完成时，双指针的长度差与双向链表的长度差完全相同。将指针B指向引用链表A的头结点，然后指向指针A。再次迭代，直到指针A遍历完成
      • 同理，将指针A指向链表B的头节点。如果指针B向前移动，链表的高度差就消除了。等于

    var getIntersectionNode = function (headA, headB) {
      if (!headA || !headB) return null;
      let pA = headA;
      let pB = headB;
      while (pA !== pB) {
        pA = pA !== null ? pA.next : headB;
        pB = pB !== null ? pB.next : headA;
      }
      return pA;
    }
    

    9，链表和

    给定链表表示的两个整数，每个节点都包含一个数字，这些数字是倒序存储的，即每个数字的位置都在链表的开头。编写一个函数对两个整数求和，并将结果作为链表返回

    示例：
      输⼊：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
      输出：2 -> 1 -> 9，即912
    
    

    步骤：

    • 解决问题的链表类型是唯一链表
    • 思路： 输出是一个新的链表，所以需要创建一个链表
    • 由于是反向存储，链表是从数字开始的，大于十就进位
    • 进位，首先考虑使用进位存放部分进位，其余部分存放在创建的节点中
  • 边界条件：
    • 如果双向链表指向：
    • 则遍历完成， 进位不为0，那么还要向前移动一位数字

  const addTwoNumbers = function (l1, l2) {
    // 哨兵
    let preHead = new ListNode(0)
    let carry = 0;
    let pre = preHead;
    while (l1 || l2) {
      let sum = 0;
      if (l1) {
        sum += l1.val
        l1 = l1.next
      }
      if (l2) {
        sum += l2.val
        l2 = l2.next
      }
      sum += carry
      carry = Math.floor(sum / 10)
      pre.next = new ListNode(sum % 10)
      pre = pre.next
    }
    if (carry > 0) {
      pre.next = new ListNode(carry)
      pre = pre.next
    }
    return preHead.next
  }
  

  进阶：思考⼀下，假设这些数位是正向存放的，⼜该如何解决呢?
    输⼊：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
    输出：9 -> 1 -> 2，即912