关于链表

链表是一种动态的数据结构，因为在创建链表时无需知道链表的长度，当插入一个节点时，只需要为新的节点分配内存，其空间效率和数组相比要高，但是每次都要创建空间所以时间不是很高

单向链表定义节点

structListNode{intm_value;ListNode*m_pNext;};

在链表后面添加节点

voidAddToTail(ListNode**pHead,intvalue)//时间效率O(N){ListNode*pnewNode=newListNode();//创建新结点pnewNode->m_value=value;pnewNode->m_pNext=NULL;if(pHead==NULL)//当头结点为空{pHead=pnewNode;}else//不为空{ListNode*pNode=*pHead;while(pNode->m_next!=NULL)//遍历找到最后一个节点{pNode=pNode->m_next;}pNode->m_next=pnewNode;}}

删除其中某节点

voidRemoveNode(ListNode**pHead,intvalue){if(pHead==NULL||*pHead==NULL)//头结点为空return;ListNode*pDelete=NULL;if((*pHead)->m_value==value){pDelete=*pHead;*pHead=(*pHead)->m_pNext;}else{ListNode*pNode=*pHead;//遍历查找要删除结点的前一个结点while(pNode->m_pNext!=NULL&&pNode->m_pNext->m_value!=value){pNode=pNode->m_pNext;}pDelete=pNode->m_pNext;pNode->m_pNext=pDelete->m_pNext;if(pDelete!=NULL){deletepDelete;pDelete=NULL;}}

题目1：

输入一个链表头结点，从头到尾反过来打印这个结点值（不改变结点结构）

程序1.0

若链表为空直接返回链表，若只有一个节点，打印此结点；若有多个结点，设置一个计数器，先、遍历结点统计结点个数，再循环结点数次，在这个循环里再依次找到倒数第一个、倒数第二个、倒数第N个节点

voidPrintListReverse(ListNode*pHead)//时间复杂度O（N^2）{while(pHead==NULL)//没有结点return;if(pHead->m_pNext==NULL)//一个节点{cout<<pHead->m_value;return;}ListNode*pNode=pHead;intcount=1;while(pNode->m_pNext!=NULL){count++;pNode=pNode->m_pNext;}while(count!=0){for(inti=1;i<count;i++){pNode=pNode->m_pNext;//找到倒数第N个节点的前一个结点}cout<<pNode->m_value<<"->";count--;}}

程序2.0

上面用循环实现，过于复杂且效率不高，所以第二次使用栈来完成，栈有“先入后出”的特性，所以用栈来实现更为方便，没遇到一个不为空的结点就把它放到栈中

voidPrintListReverse(ListNode*pHead)//时间复杂度O(N){stack<ListNode*>s1;ListNode*pNode=pHead;while(pNode->m_pNext!=NULL){s1.push(pNode);pNode=pNode->m_pNext;}while(!s1.empty()){cout<<s1.top()->m_value<<"->";s1.pop();}}

程序3.0

我们知道递归的本质就是栈，所以我们也可以用栈来实现它，先递归后面的结点，一直递归到没有结点，再输出该结点

voidPrintListReverse(ListNode*pHead){if(pHead!=NULL){if(pHead->m_pNext!=NULL)//递归停止条件{PrintListReverse(pHead->m_pNext);}cout<<pHead->m_value<<"->";}}

递归写法虽然看起来要简洁的多，但是若结点超级长则会导致函数调用栈溢出，所以在实现是最好使用显示调用栈的方式来实现

题目2：

题目：在O（1）的时间删除链表结点

分析：要删除一个节点，O（n）的方法是从头到尾遍历找到要删除的结点（即顺序查找），并在链表中删除它。

程序1.0 删除一个节点复杂度O（n）

voidDeleteNode(ListNode**pListHead,ListNode*pToBeDeleted){if(pListHead||pToBeDeleted)return;ListNode*cur=*pListHead;while(cur->m_pNext!=pToBeDeleted){cur=cur->m_pNext;}cur->m_pNext=pToBeDeleted->m_pNext;deletepToBeDeleted;}

程序2.0

删除一个结点复杂度O（1），找到要删除的结点pToBeDelete的后面的结点del，把这个结点的值覆盖要删除的结点，删除这个后面的结点

voidDeleteNode(ListNode**pListHead,ListNode*pToBeDeleted){if(pListHead||pToBeDeleted)//若为空return;if((*pListHead==pToBeDeleted)&&(pToBeDeleted->m_pNext==NULL))//只有一个节点且删除这个结点{deletepToBeDeleted;pToBeDeleted=NULL;*pListHead=NULL;return;}if(pToBeDeleted->m_pNext==NULL)//有多个结点pToBeDeleted为尾节点O(N){ListNode*cur=*pListHead;while(cur->m_pNext!=pToBeDeleted){cur=cur->m_pNext;}cur->m_pNext=NULL;deletepToBeDeleted;pToBeDeleted=NULL;}elseif(pToBeDeleted->m_pNext)//有多个结点且pToDeleted不为尾{ListNode*del=pToBeDeleted->m_pNext;pToBeDeleted->m_value=del->m_value;pToBeDeleted->m_pNext=del->m_pNext;deletedel;del=NULL;}}

题目3：

输入一个链表，输出链表中倒数第K个节点

分析：定义两个指针均指向头，一个指针先走K步，另一个等第一个指针走k步后再和其一起走，知道第一个走到空时第二个指针即走到倒数第k个节点

考虑：1.输入的头结点是否为空，访问空指针指向的内存导致程序奔溃2.链表的结点是否大于k3.k若为0怎么办

ListNode*FindKthToTail(ListNode*pHead,intk){if(pHead==NULL||k==0)returnNULL;ListNode*fast=pHead;ListNode*slow=pHead;while(--k){if(fast->m_pNext!=NULL)fast=fast->m_pNext;elsereturnNULL;}while(fast->m_pNext){slow=slow->m_pNext;fast=fast->m_pNext;}returnslow;}

相似快慢指针问题

1.题目：求链表中间结点

设置指向头的快、慢指针，快指针每次走两步，慢的每次走一步，当快指针走到末尾时，慢指针刚好在中间

ListNode*FindMidNode(ListNode*pHead){if(pHead==NULL)returnNULL;ListNode*fast=pHead;ListNode*slow=pHead;while(fast->m_pNext&&fast){fast=fast->m_pNext->m_pNext;slow=slow->m_pNext;}returnslow;}

2.判断一个指针是否构成环形

同上方法，如果带环，则快指针一定会追上慢指针，若快指针走到了链尾（NULL），则不是环形链表

ListNode*IsCircleList(ListNode*pHead){if(pHead==NULL)returnNULL;ListNode*fast=pHead;ListNode*slow=pHead;while(fast&&fast->m_pNext){fast=fast->m_pNext->m_pNext;slow=slow->m_pNext;if(slow==fast)returnslow;}returnNULL;}

题目4：

反转链表

voidReverseList(ListNode*pHead){if(pHead==NULL||pHead->m_pNext==NULL)return;ListNode*newHead=NULL;ListNode*cur=pHead;ListNode*prev=pHead;while(cur){prev=cur;cur=cur->m_pNext;prev->m_pNext=newHead;newHead=prev;}pHead=newHead;}

题目5：

合并两个排序的链表

ListNode*Merge(ListNode*pHead1,ListNode*phead2){if(pHead1==NULL)returnphead2;if(phead2==NULL)returnpHead1;ListNode*newHead=NULL;while(pHead1&&phead2){if(pHead1->m_value<phead2->m_value){newHead=pHead1;newHead->m_pNext=Merge(pHead1->m_pNext,phead2);}else{newHead=phead2;newHead->m_pNext=Merge(pHead1,phead2->m_pNext);}}returnnewHead;}