链表🐑

反转链表

题目描述：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

链接：https://leetcode-cn.com/problems/reverse-linked-list/

解法：

• 方法一：迭代法

  • 思路：设置一个前指针prev和推进指针curr,直到curr为空，返回prev
  • 复杂度分析:
    • 时间: O(n). 逐个推进故 O(n).
    • 空间: O(1). 只用到了常数级额外空间故 O(1).

  • 代码

    var reverseList = function(head) {
    let [prev, curr] = [null, head];
    while (curr) {
       let temp = curr.next;    // 1. 临时存储当前指针后续内容
       curr.next = prev;       // 2. 反转链表
       prev = curr;            // 3. 接收反转结果
       curr = temp;             // 4. 接回临时存储的后续内容
    }
    return prev;
    };

  • 优化代码

    var reverseList = function(head) {
    let [prev,curr]=[null,head]
    while(curr){
       [curr.next,prev,curr]=[prev,curr,curr.next]
    }
    return prev
    }

• 方法二：尾递归法

  • 思路：用prev和curr存储推进状态，直到curr为空输出结果
  • 复杂度分析:
    • 时间: O(n). 等同于正常推进，故 O(n).
    • 空间: O(1). 尾递归方式，重复使用一个空间故空间复杂度为 O(1).
  • 代码

    var reverseList=function(head){
    reverse(null,head)
    }
    function reverse(prev,curr){
    if(!curr) return prev
    let temp=curr.next 
    curr.next=prev
    return reverse(curr,temp)
    }

• 方法三：转成数组后通过reduce构造出链表

  • 复杂度分析：
    • 时间：O(n):两轮遍历
    • 空间：O(1):结果不算额外空间，是非原地反转算法
  • 代码

    var reverseList=function(head){
    if(!head || !head.next) return head
    const array=[]
    while(head){
     array.push(head.val)
    head=head.next
    }
    return array.reduce((item,v)=>{return {val:v,next:item}},null)
    }

    合并两个有序链表

    题目描述：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

    链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/

    解法：

• 方法一：递归法

  • 思路：
    • 可以用递归来实现，新的链表不需要构造新的节点
    • 递归终止条件：两个链表中只要有一个链表为空就结束
    • 返回值：返回每一层调用都返回排序好的链表头
    • 本级递归内容：如果第一个链表的 val 值更小，则将 第一个链表的next 与排序好的链表头相接，第二个链表同理
  • 代码

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

    相交链表

    题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

    示例：

    图示两个链表在节点 c1 开始相交：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at ‘8’ 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。

链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/

解法：

• 方法一：哈希表

  • 思路：
    • 先遍历一遍链表 A，用哈希表把每个节点都记录下来(注意要存节点引用而不是节点值)。
    • 再去遍历链表 B，找到在哈希表中出现过的节点即为两个链表的交点
  • 复杂度分析：
    • 时间复杂度：O(M + N)O(M+N), M, N 分别为两个链表的长度。
    • 空间复杂度：O(N)O(N)，N 为链表 A 的长度
  • 代码:

    var getIntersectionNode = function(headA, headB) {
    if(!headA||!headB) return null 
    const hashMap=new Map()
    while(headA){
       hashMap.set(headA,1)
       headA=headA.next 
    }
    while(headB){
       if(hashMap.has(headB)) return headB
       headB=headB.next
    }
    };

• 方法二：暴力法

  • 思路：
    • 对于链表 A 的每个节点，都去链表 B 中遍历一遍找看看有没有相同的节点。
  • 复杂度分析：
    • 时间复杂度：O(M * N)O(M∗N), M, N 分别为两个链表的长度。
    • 空间复杂度：O(1)O(1)。
  • 代码

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

    链表的中间节点

    给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

    链接：https://leetcode-cn.com/problems/middle-of-the-linked-list/

    解法：

• 方法一：数组法

  • 思路：
    • 由于链表无法通过下标来访问对应的元素，因此可以采用数组来存储元素，利用数组的下标来找到数组的中间节点位置。
    • 将链表依次放入数组中，数组的每个元素用来存放起始的node，链表每向后next且不为null，则将该数组元素的next push进数组。
    • 用数组的长度判断数组的末尾，链表全部遍历完成即为数组的长度
    • 最后返回数组长度（也就是链表长度）的中间值作为数组元素，也就是中间节点

      var middleNode = function(head) {
      const newArr=[head]
      while(newArr[newArr.length-1].next){
      newArr.push(newArr[newArr.length-1].next)
      }
      return newArr[newArr.length>>1]
      };

• 方法二：快慢指针法

  • 思路
    • 既然是链表的中间点，那就可以设想一个指针遍历到末尾，另一个指针用它的一半速度遍历

即一个指针一次两步step2，另一个指针一次一步step1
同时要考虑链表长度奇偶性对中间点的影响
在长度n为奇数时，n-1为偶数，step1到达中点时step2恰好到达终点
此时需要判断step2.next为null，以终止遍历
在长度n为偶数时，n-1为奇数，step1到达中点时step2恰好越界为null
此时需要判断step2是否为null，终止遍历

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

删除链表倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

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

解法：

• 方法一：快慢指针
  • 思路：
    • 将slow，fast赋值为head
    • 然后将fast后移n步
    • 接着快慢指针fast，slow一起向后移动，直到fast.next===null
    • 此时slow.next就是要删除的结点，删除即可
    • 注意⚠️：当fast后移n步时，如果题目给的n与链表中总的结点个数相同时，也就是要删除头结点，那么fast会移动到链表外面，即fast===null，即可通过fast是否为空来决定要不要直接返回结果

      var removeNthFromEnd = function(head, n) {
      let slow=head,fast=head
      // 先让 fast 往后移 n 位
      while(n--){
      fast=fast.next
      }
      // 如果 n 和 链表中总结点个数相同，即要删除的是链表头结点时，fast 经过上一步已经到外面了
      if(!fast){
      return head.next
      }
      // 然后快慢指针一起往后遍历，当 fast是链表最后一个结点时，此时slow下一个就是要删除的结点
      while(fast.next){
      slow=slow.next
      fast=fast.next
      }
      slow.next=slow.next.next
      return head
      };