LeetCode题集整理- 链表篇

1、链表基础

• 链式存储方式线性表

  • 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的.
  • 优：删除还插入效率高
  • 缺：查询效率低

• 循环链表

  • 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表.
  • 双向循环链表是单向循环链表的每个结点中，再设置一个指向其前驱结点的指针域

• 1、单链表的打印

  
  

• 2、链表的逆序

• 3、已知链表的头节点指针head，将链表从位置m到n 逆序（不可申请额外的空间）。

• 4、已知链表A的头节点指针headA,链表B的头节点指针headB， 两个链表相交，求两个链表交点对应的节点。

• 思路1:使用set求交集
  • 遍历链表A ，将A中节点对应的指针地址，插入set.

  • 遍历链表B，将B中节点对应的指针地址，在set 中查找，发现在set 中的第一个节点地址，既是两个链表的交点。

    
    
• 思路2：
  • 计算headA 链表的长度、计算headB链表的长度，较长的链表多出的长度。
  • 将较长链表的指针移动到和较短链表指针对齐的位置
  • 将headA 与headB同时移动，当两个指针指向同一个节点时，找到了。

• 5、已知链表可能存在环，若有环返回环起始节点，否则返回NULL

• 思路1:使用set求交集
  • 遍历链表 ，将链表中节点对应的指针地址，插入set.
  • 在遍历链表时，在set 中查找，第一个在set 中发现的节点地址，既是链表的起点。

• 思路2:快慢指针赛跑
  • 快指针每次走2步，慢指针走1步.
  • 如果有环，必定相遇。从head与meet 出发，两指针速度一样，相遇时即为环的起点。

• 6、已知链表头指针与数值x,将所有小于x 的节点放在大于或者等于x的节点前，且保持这些节点的原来的相对位置。

• 思路：巧用临时头节点。

• 7、已知一个复杂的链表，节点中有一个指向本链表任意某个节点的随机指针，求这个链表的深度拷贝。

前期的准备工作：

• 设置一个节点map,key为节点地址，value为整型。

思路：

• 难点在于：将原链表的random指针的指向关系理清楚，如何保存。

• 知识储备：

  • vector是表示可变大小数组的序列容器。

  • 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

  • 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

  • vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

  • 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

  • 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

  • 多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值

  • 末尾添加元素： vec.push_back();

  • 末尾删除元素： vec.pop_back();

  • 任意位置插入元素： vec.insert();

  • 任意位置删除元素： vec.erase();

  • 交换两个向量的元素： vec.swap();

  • 清空向量元素： vec.clear();

• 1： 创建地址到节点位置的map。
• 2: 使用Vector根据存储节点位置访问地址。
• 3: 循环遍历，将新链表节点push 入node_vec，生成了新链表节点位置到地址的map。
• 4: 记录原始链表地址至节点位置的node_map。
• 5: 遍历原始链表。
• 6: 记录节点位置。

• 7: 再次遍历原始链表，链接新链表的next指针，random 指针。

  
  

• 8、已知两个已排序链表头节点指针式headA ,headB,将两个链表合并，合并后仍为有序的，返回合并的头节点。

• 思路： 建立一个临时头节点 temp_head. 然后让pre指针指向该节点。 比较headA,headB指向的节点，将较小的节点插入pre 指针后，并向前移动较小节点对应的指针。

• 9、已知K个已排序链表头节点指针，将这K个链表合并，合并后仍为有序的，返回合并后的头节点。

方案1:

方案2：