Krahets 笔面试精选 88 题

# 一、链表

# 合并两个升序链表为一个升序链表

题目open in new window

# 1.搞清什么是链表和升序链表

• 链表：一种线性数据结构，由一系列节点组成。每个节点包含数据和指向下一个节点的引用（也称指针，不同编程语言英文不同，但一般多用next表示）。节点在内存中不连续，而是通过next找到并连接。
• 升序链表：节点所储存的数据是从小到大排列的。
• 链表的指针：next，一个链表可能由一个或多个指针，这是由链表类型和节点判断，如单向链表中每个节点只有一个指针，双向链表每个节点由两个指针。

function listNode(val){
  this.val = val //.val节点中的数据
  this.next = null //.next 节点指针指向

}

# 2.搞清链表的数据访问特点 => 如何判断链表为空

这一步是为了判断两个升序链表是否为空的关键。

• 链表不同于数组的访问方式，数组通过下标访问数据，链表通过指针指向。注意链表访问必须依赖指针顺序访问，从链表头部节点开始。
• 如何判断链表是否为空？根据上条，判断头部节点是否为空即可。l1.next===null但程序中，当提到一个链表，通常通过头部指针代它，所以可以简化为l1===null

# 3.解决关键：递归思想

在计算机科学中指一种通过重复将问题分解为同类的子问题而解决问题的方法。特点是在过程或函数里调用自身。

var mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {
        //取出头节点l1的数据,解决子问题，合并l1.next和l2
        l1.next = mergeTwoLists(l1.next, l2);//l1.next指向子问题的结果
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

# 4.拓展知识

• 链表历史：无明确发明者。历史上对链表发展有重要贡献的是高德纳open in new window，1973年首创双向链表，著《计算机程序设计的艺术》。链表起源追溯20C50S，科学家为解决数组在插入、删除操作中的效率问题，研究和发展出链表结构。

• 题干中-100 <= Node.val <= 100是什么意思?限制条件，以确保节点值的范围在-100到100之间。这样的限制有助于简化问题的复杂度，避免处理超出预期范围的数据，从而使得算法更加高效和可靠。

# 反转链表

# 1.链表的最后一个节点都指向空吗？(解题while中的条件思路：当cur指向空 结束循环)

常见的单链表结构中，最后一个节点的指针指向空（null）,这是单链表表示链表结束的一种方式。但循环链表的最后一个节点指向链表的第一个节点或其他节点，形成环形结构。

所以，链表的最后一个节点是否指向空，取决于链表的类型。

# 2.解决关键：迭代思想

一种不断用变量的旧值递推新值的过程。迭代对应的是直接法（一次性解决问题）。迭代法利用计算机运行速度快、适合做重复性操作的特点，让计算机对一组指令重复执行。

如在MDN中，对while(condition){statement}，官方给的解释是只要condition条件为真，while语句就会一直迭代。

//这道题可以用递归的方法去解，但我看不懂，刷一遍再说吧
while(  ){
  
}

linkopen in new window