list

开始内功！

前几日和前老大谈了谈，总结起来内功不能不练。实习以来有三次想好好复习数据结构和算法，但是最后都半途而废。现在不应该再有任何理由了，不然以后再也没有时间好好去复习这些东西。从现在开始刷好题目，打好基础。

##链表

链表是线性表的一种。

线性表是最简单基础的一种数据结构。线性表中的数据元素之间的关系是一对一的，除了头元素和尾元素之外，其他元素首尾相连。线性表有两种存储方式

1. 顺序存储方式
2. 链式存储方式

数组是典型的顺序存储方式。链表是典型的链式存储方式。

链式存储结构，指的是相邻的两个元素在内存中可能不是相邻的，每一个元素都有一个指针域，指针域存放的是下一个元素的指针。

链式结构的优缺点：

• 优点

  1. 插入和删除的复杂度为O(1)
  2. 不会浪费太多内存，在需要添加元素的时候才会申请内存，删除元素后释放内存。

• 缺点

  1. 访问元素的时间复杂度最坏为O(N)

  链表就是链式存储的线性表。根据指针域的不同，链表分为单项链表，双向链表，循环链表等等

  一个简单的List定义

  struct list {
      int ver;
      struct list *next;
  };
  typedef struct list *listLink;
  // 插入
  void insert_list(listLink *, int);
  // 打印
  void print_list(listLink *, int);
  // 链表长
  int list_length(listLink);
  // 搜索一个特定的值
  listLink search_list(listLink, int);

四个方法的实现

##指针常出现的问题

###反转链表

反转链表，分为两种情况讨论，单向链表和双向链表

• 单向链表

  • 考虑到访问某个节点的时候，要检查下一个节点是否为空。

  • 要把反转后的最后一个节点（头节点）的指针指向null

实现代码如下

• 双向链表

双向链表比较麻烦的地方在于Next和pre要呼唤，需要主要当前节点和上个节点的问题。

###删除节点

删除节点必须要知道被删除节点的前置节点，时间复杂度为O(1)

###循环链表

循环链表表现于尾元素的next指针指向head元素，所以我们可以通过快慢指针去校验。具体的方法会在下面的链表的技巧中提到.

链表的技巧

###鲁棒性

• 当访问链表中某个节点的next节点的时候，一点要先判断当前节点是否为空。
• 全部操作结束后，判断是否有环。若有环，则置其中一端为Null;

Dummy Node

假节点，伪头节点。Dummy Node 可以认为是一个假的头结点。我们可以构造一个Dummy Node ，使他的next指针指向Head node。使用Dummy Node目的是，在单向链表中，保正head不会再删除操作中丢失。此外，比较特殊的方法是用来进行删除head。

Dummy Node可以处理对于head Node变化的情况。

快慢指针

快慢指针式解决很多链表的问题的关键。快慢指的是指针每次移动的步长。常用的快指针步长为2，慢指针步长为1.快慢指针同时从头结点开始移动陪你过。

快慢指针的应用可以解决以下问题

1. 快速找出为止长度的链表的中间节点。我们让快指针的步长是慢指针的两倍。当快指针到达尾节点的时候，慢指针所指向的节点就是中间节点。
2. 判断单向链表是否成环。同样的原理，如果快指针 *fase =NULL的时候，说明链表是NULL结尾的。如果快指针等于慢指针的时候，则说明该链表成环。

赏

谢谢你请我吃糖果