您的位置:  首页 > 技术杂谈 > 正文

单链表解题思维

2022-02-16 15:00 https://my.oschina.net/jill1231/blog/5447093 花木喔 次阅读 条评论

一、概念

链表由一组零散的结点通过指针连接而成,每个结点都包含当前结点内容和后继指针。相对于数组,它不受固于存储空间的限制,可更快捷地进行插入和删除操作,主要有以下几种类型:

1、单链表

指针指向下一个节点,终点指向null

2、双链表

指针指向前一个节点和后一个节点

3、循环链表

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

在解决链表相关问题时,先执行三步骤,再敲下代码会更清晰

  • 确定解题的链表类型
  • 画图理清思路
  • 确定边界条件

不同于数组,JS官方还没有提供一个直接的链表API,可通过对象的方式模拟出链表,其结构为

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

二、leetcode 最常见相关题型

1、合并两个有序链表

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

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

步骤:

  • 解题的链表类型是单链表
  • 思路:
    • l1l2 是有序递增的,因此 l1.vall2.val 的较小值就是合并后链表的最小值
    • 依次递归 大小节点的比较,直到 l1 l2 均为 null
  • 边界条件:递归到任意链表为 null 即可停止,并将 next 指向另外的链表
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  // 链表中有一个环,其尾部连接到第二个节点

步骤:

  • 解题的链表类型是单链表
  • 思路:
    • 龟兔赛跑算法:利用快慢双指针,快指针走两步,慢指针走一步
    • 如果链表存在环,则两个速度不同的指针必定会相遇。并且从相遇点和链表头结点同时往下走,会在环起点相遇
  • 边界条件:
    • 快指针指向 null 停止,无环
    • 快慢指针指向同一个节点,有环
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、反转链表

给你单链表的头节点 head ,请你使用迭代或递归地反转链表,并返回反转后的链表

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

步骤:

  • 解题的链表类型是单链表
  • 迭代思路:
    • 将单链表的每个节点的后继指针指向它的前驱节点

  • 边界条件:
    • 当链表 null 停止
    • 链表仅有一个节点
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、链表的中间结点

给定一个头结点为 head 的非空单链表,返回链表的中间结点,如果有两个中间结点,则返回第二个中间结点(给定链表的结点数介于 1 和 100 之间)

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

步骤:

  • 解题的链表类型是单链表
  • 思路:
    • 快指针p2的位移是慢指针p1的2倍,所以当p2走到链表尾部时,p1刚好走了一半,指向链表的中点。
    • 下题同理

  • 边界条件:
    • 快指针指向 null 时,慢指针刚好处于中间位置
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
};

5、删除链表倒数第 n 个结点

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

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

步骤:

  • 解题的链表类型是单链表

  • 思路:

    • 快指针一次性走完n个节点,接着两个指针一起往后走,直到快指针指向null,此时慢指针就是倒数第n个节点
    • 添加哨兵处理第n个节点
  • 边界条件:

    • 快指针指向 null 时,慢指针所在位置就是倒数第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、回文链表

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false

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

步骤:

  • 解题的链表类型是单链表

  • 思路:

    • 借助数组,将链表丢进数组
    • 设置前后指针,前后指针理应相同,若不同则不是回文
    • 循环结束若没有返回false则是回文
  • 边界条件:

    • 前后指针不一致
    • 循环结束
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
}

8、相交链表

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。题目数据保证整个链式结构中不存在环。

注意:

  • 函数返回结果后,链表必须 保持其原始结构(需复制新的链表)
  • 如果两个链表没有交点,返回 null
  • 程序尽量满⾜ 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指针向前一步,则消除了链表的高度差

  • 边界条件:
    • 指针指向null时,切换指向链表
    • AB链表值相等
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

步骤:

  • 解题的链表类型是单链表

  • 思路:

    • 输出的是新链表,因此需要创建一个链表
    • 由于是反向存储,则链表从个位数开始计算,大于十则进位
    • 进位,首先考虑⽤carry存储每次的进位,余数存储进创建的节点
  • 边界条件:

    • 双链表指向null时,遍历完成
    • 遍历完成,carry不为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
展开阅读全文
  • 0
    感动
  • 0
    路过
  • 0
    高兴
  • 0
    难过
  • 0
    搞笑
  • 0
    无聊
  • 0
    愤怒
  • 0
    同情
热度排行
友情链接