基础概念：
节点（Node）是其中的元素，相邻节点彼此互称前驱（predecessor）或后继（successor）；
没有前驱/后继的唯一节点称为首（first/front）/末（last/rear）节点
头（header）、尾（trailer）两个哨兵
1、单向链表（One-way LinkedList）
定义：一个序列中只含有指向它的后继结点的链接时，就称该链表为单链表。
每一个链表有一个头指针，通过头指针可以找到第一个节点，每个节点都可以通过指针域找到它的后继，最后一个节点的指针域为NULL，表示没有后继，即最后一个没有指向。
考查知识点：查找、删除、插入
/*单向链表节点定义*/
struct Node
{
int val;
Node * pnext;
};
当我们往一个空链表中插入一个节点时，新插入到节点就是链表的头指针，此时会改动头指针，因此必须把phead参数设置为指向指针的指针。
/*在链表末尾添加一个新节点*/
void AddToTail(Node ** phead,int value)//phead是一个指向指针的指针
{
Node * pnew=new Node();//为新节点开辟空间
pnew->val=value; //新节点数据域赋值
pnew->pnext=NULL;//新节点指针域置空
if(*phead==NULL) *phead=pnew；//空链表，则新节点为首节点
else
{
Node * pnode=*phead;
while(pnode->pnext != NULL) pnode=pnode->pnext;
pnode->next=pnew;//从首节点出发，不断往后继找，直到找到后继
//指针域为空的节点，将新节点的指针赋给找到的那个节点的后继
}
}
/*在单链表中间位置插入一个节点*/
链表中的内存不是一次性分配的，故内存不连续，所以无法寻秩访问。
查找时间效率为O（n）。
思路：①创建待删除节点存储空间；②若首节点即为查找节点，将首节点指针赋给待删除节点指针，首节点的后继作为首节点；③若查找节点在链表中间，创建节点等于首节点，沿next指针直至找到“节点后继数据”为待查找数据；④找到后，当前节点后继给之前创建的待删除指针，当前节点的后继的后继作为当前节点的后继；⑤待删除指针被赋值后，销毁（delete+置空）；
/*查找并删除节点*/
void RomoveNode(Node **phead,int value)
{
if(phead==NULL || *phead==NULL) return;
Node * pTobeDeleted =NULL;//①
if(phead->val==value)//①
{
pTobeDeleted=*phead;
*phead=(*phead)->pnext;
}
else
{
Node *pnode=*phead;//③
while(pnode->next!=NULL && pnode->pnext->val != value)
pnode=pnode->pnext;
if(pnode->pnext != NULL && pnode->pnext->val == value)//④
{
pTobeDeleted=pnode->pnext;
pnode->pnext=pnode->pnext->pnext;
}
}
if(pTobeDeleted!=NULL)//⑤
{
delete pTobeDeleted;
pTobeDeleted=NULL;
}
}
剑指offer-5-从尾到头打印链表
思路：从头到尾遍历链表，将遍历到的节点放入栈中，遍历完成，从栈中取出。
①创建栈；②创建节点pnode，指向首节点；③当链表不为空时，取出当前节点压入栈中+当前节点传递到后继节点；④从栈顶元素开始，先将其交给节点pnode，打印其数据域，再弹出（在这一过程中栈顶元素后移，注意先后顺序），直至栈变空；
void PrintListReversingly_Iteratively(Node *phead)
{
stack<Node *> nodes;
Node *pnode=phead;
while(pnode!=NULL)
{
nodes.push(pnode);
pnode=pnode->pnext;
}
while(!nodes.empty())
{
pnode=nodes.top();
cout<<pnode->val;
nodes.pop();
}
}
递归在本质上是一个栈结构，也可以用递归实现，但存在链表非常长的时候，递归调用层级很深，导致函数调用栈溢出。
剑指offer-13-在O(1)时间内删除链表节点
题目：给定单向链表的头指针和一个节点指针，定义一个函数在O（1）时间删除该节点。
首先需要明确的是，要删除链表中的节点，必须找到该节点的前驱，通过将前驱指针指向该节点的后继，才能删除；若如此，需要遍历，时间为O（n）；
改进思路：通过待删除节点i找到待删除节点i的下一个节点j，将j的内容复制到i内，删除j节点，把i的指针指向j的下一个节点，此时再删除节点j。
以上思路不适用于待删除节点为尾节点时的情况。
同时考虑链表为空和链表只有一个元素的情况
void DeleteNode(Node ** phead,Node * pTobeDeleted)
{
//链表非空、待删节点非空
if(!phead || !pTobeDeleted) return;
//若所删节点不是尾节点
if(pTobeDeleted->next != NULL)
{
Node *pDnext = pTobeDeleted->pnext;
pTobeDeleted->val = pDnext->val;
pTobeDeleted->next = pDnext->pnext;
delete pDnext;
pDnext=NULL;
}
//链表只有一个节点，删除头节点（同时也是尾节点）
else if(*phead==pTobeDeleted)
{
delete pTobeDeleted;
pTobeDeleted = NULL;
*phead = NULL;
}
//链表中有多个节点，删除尾节点
else
{
Node * Pnode=*phead；
while(Pnode->pnext != pTobeDeleted)
{
Pnode=pnode->pnext;
}
Pnode->pnext = NULL;
delete pTobeDeleted;
pTobeDeleted=NULL;
}
}
剑指offer-15-链表中倒数第k个节点
<单向链表无法从后往前找>
思路①：遍历链表两次，第一次确定链表长度n，第二次遍历定位到n-k+1个；
思路②：遍历链表一次，定义两个指针，第一个指针从链表的头指针开始遍历向前走k-1步，第二个指针保持不动；从第k步开始，第二个指针开始从链表的头指针开始遍历。（保持两者的距离为k-1）
写代码要注意鲁棒性。
此题有以下三种情况可能导致代码崩溃：
①phead为空指针，代码试图访问空指针指向的内存，程序崩溃；
②链表节点数目少于k，依然会导致空指针问题；
③输入的参数为0；
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(pListHead == NULL || k == 0) return NULL;
ListNode * pAhead = pListHead;
ListNode * pBehind = NULL;
for(unsigned int i=0;i<k-1;i++)
{
if(pAhead->next != NULL)
pAhead=pAhead->pnext;
else
return NULL;
}
pBehind=pListHead;
while(pAhead->pnext != NULL)
{
pAhead=pAhead->pnext;
pBehind=pBehind->pnext;
}
return pBehind;
}
可拓展至：
①求链表的中间节点，双指针解决：一个指针走一步，一个指针走两步，同时出发；
②判断一个单向链表是否形成了环形结构，双指针解决：一个指针走两步，一个指针走一步，同时出发，如果在走一步的的指针走到链表末尾时都没有遇见走得两步的，那么链表就不是环形链表。
剑指offer-16-反转链表
思路：定义三个指针，分别指向当前节点、前驱节点及后继节点。将当前节点的next指向前驱节点，同时，事先需要准备保存i的后继，以防止链表断开。
测试用例：
①链表为空；
②链表只有一个节点；
③链表有多个节点。
ListNode* ReverseList(ListNode* pHead) {
ListNode * pReverseHead =NULL;
ListNode * pNode=pHead;
ListNode * pPrev=NULL;
while(pNode != NULL)
{
ListNode * pNext=pNode->next; //用于保存当前节点的后继
if(pNext==NULL) pReverseHead=pNode;
pNode->next=pPrev; //next指针反转，指向当前节点的前驱
pPrev=pNode; //当前节点变成它之前前驱的前驱
pNode=pNext; //后继变成当前节点
}
return pReverseHead;
}
剑指offer-17-合并有序列表
递归思想
测试用例：
①链表1为空或链表2为空；
②正常链表。
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL) return pHead2;
if(pHead2 == NULL) return pHead1;
ListNode * pMergeHead =NULL;
if(pHead1->val < pHead2->val)
{
pMergeHead=pHead1;
pMergeHead->next=Merge(pHead1->next,pHead2);
}
else
{
pMergeHead=pHead2;
pMergeHead->next=Merge(pHead1,pHead2->next);
}
return pMergeHead;
}
剑指offer-37-两个链表的第一个公共节点
明确：节点具有数据域和指针域，若两节点相同，则两个域的内容
也相同，即指向的下一个节点也相同。
测试用例：
①公共节点的位置（中间、首、尾、没有公共节点）；
②链表头节点是NULL指针。
class Solution {
public:
unsigned int GetListLength(ListNode * phead)
{
unsigned int length=0;
ListNode*pnode=phead;
while(pnode->next != NULL)
{
length++;
pnode=pnode->next;
}
return length;
}
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1==NULL ||pHead2==NULL ) return NULL;
unsigned int length1=GetListLength(pHead1);
unsigned int length2=GetListLength(pHead2);
int lengthDif=length1-length2;
ListNode* pListHeadLong=pHead1;
ListNode* pListHeadShort=phead2;
if(length1<length2)
{
lengthDif=length2-length1;
pListHeadLong=pHead2;
pListHeadShort=pHead1;
}
for(int i=0;i<lengthDif;i++) //长链表先遍历长度差步
{
pListHeadLong=pListHeadLong->next;
}
while((pListHeadLong!= NULL) && (pListHeadShort != NULL) && (pListHeadLong != pListHeadShort))
{
pListHeadLong=pListHeadLong->next;
pListHeadShort=pListHeadShort->next;
}
ListNode* pFirstCommonNode = pListHeadLong;
return pFirstCommonNode;
}
};
2、双向链表
在单链表的每个结点中，再设置一个指向其前驱节点的指针域。
/*双向链表存储结构*/
struct ListNode
{
int val;
ListNode * front;
ListNode * next;
};
双链表反向查找结点优于单链表 ，实质上是以空间换取时间.
缺点：在插入和删除一个结点时需要维护两个指针变量，特别是在双链表的插入中指针的指向顺序是不可修改的。
双向链表的插入
image.png
/*双向链表插入*/
1 NewNode->front = p；
2 NewNode->next = p->next;
3 p->next->front = NewNode;
4 p-next = NewNode;
双向链表的删除
image.png
/*双向链表删除*/
1 p->front->next = p->next；
2 p->next-front = p->front;
剑指offer-27-二叉搜索树与双向链表
网友评论