链表的特性

链表由节点构成，节点=数据域+指向下一个节点内存地址的指针域构成。

物理上存储非连续，数据结构的逻辑顺序通过指针实现。它在循环遍历和查找时效率不高，但插入和删除时间复杂度可达到O(1)。

优点：建立时无需预先分配储存空间，插入删除时无需移动大量数据。

单链表常用操作

1、创建、插入和删除

前插创建：malloc指针pInsert，pInsert->next指向pHead->next；pHead->next指向pInsert

尾插创建：pTail用于保存链表尾指针，初始pTail = L（L->next = NULL），循环插入新节点：malloc新节点pInsert，pTail->next = pInsert，pTail = pInsert，循环结束后pTail->next置为NULL。

在第i个节点插入：定义pPre前驱节点，循环i - 1次pPre = pPre->next后，pInsert->next = pPre->next，pPre->next = pInsert。

删除值为x的节点：定义pPre前驱节点和pDelete要删除的节点，循环p-data != x赋值pPre = p，p = p->next，结束后前驱节点直接指向要删除节点的next：pPre->next = pDelete->next

2、求节点个数（链表长度），复杂度O(n)

判断pHead != NULL不是空链表；

定义长度length = 0、pCurrent = pHead；

while条件pCurrent != NULL，循环pCurrent = pCurrent->next，length++；

return length。

3、单链表反转，复杂度O(n)

判断pHead != NULL不是空链表，否则直接返回原空链表头指针；

定义反转后的新链表头指针pNewHead = NULL，pCurrent = pHead；

while条件pCurrent != NULL，循环：pTemp存起当前节点指针，当前节点指针pCurrent替换成下一个节点的指针pCurrent->next，pTemp的next指向pNewHead，pTemp赋值给pNewHead。（即，每一次循环都是1、将当前节点指向下一节点；2、新头节点的next指向旧头节点；3、新链表的头节点永远指向当前节点）

4、查找倒数第K个节点，复杂度O(n)

�原理：一前一后两个指针，ahead，behind，ahead先走到第K个节点与behind造成K个节点的差值，之后同时移动直到ahead->next = NULL，返回behind即倒数第K个节点

同理可查找链表的中间节点（前指针走两步，后指针走一步，得到第n/2 + 1个节点）

5、从尾到头打印，复杂度O(n)

原理：使用栈，后进先出。递归输出pHead->next。

6、合并单链表，复杂度O(max(len1, len2))

类似归并排序。

首先判断两链表都不为空；

定义合并后的链表的头指针pHeadMerged = NULL，pHead1和pHead2比较后，赋值给pHeadMerged后，指向next；

定义pTemp = pHeadMerged，以p1 && p2都不为NULL为条件循环，p1p2判断后赋值给temp->next（即赋值给pHeadMerged->next），p1p2自身指向next，temp指向temp->next，temp->next指向NULL；

若p1或p2其中一个为NULL，则temp->next指向p1或p2，直接接入剩余链表

也可以使用递归的解法（比较耗费空间但更简洁更容易理解）。

p1p2判断后赋值给pHeadMerged（初始为NULL）；

pHeadMerged->next = 递归函数（p1->next/p2->next, p2/p1）

7、判断是否有环，复杂度O(n)

最笨的方法是每次取一个节点循环遍历比较，复杂度O(n²)，显然不够优雅

是否存在：应使用一快一慢两个指针pFast每次前进两步，pSlow每次前进一步，相遇（pFast == pSlow）即有环。

环长度：第一次相遇开始计数，第二次相遇结束时即环的长度。ps：总长度 = 环长度+头指针到环入口的距离。

环入口：定理，碰撞点到连接点的距离 = 头指针到连接点的距离。分别从碰撞点和头指针开始走，相遇即连接点。

8、判断两单链表是否相交，复杂度O(len1+len2)

原理：相交的单链表尾节点相同，遍历第一个链表，保存尾指针，遍历第二个判断是否尾指针相同，空间复杂度O(1)。

求相交的第一个节点：先将长的链表遍历到len1- len2的节点，此时，两链表到第一节点距离相等，然后一起开始遍历，直到两个节点地址相同即为第一个相交的节点。