链表是一种最简单的数据结构之一，经常会被面试官用来考察应聘者的基础扎不扎实，最近也到了求职季，所以我把自己对链表的一些理解写出来，希望能跟大家交流交流；
链表的概念其实挺简单，无非就是一个利用指针将数据元素顺序串联起来的一种非连续、非顺序的存储结构；链表中每一个结点都包含两个部分：一个室存储数据的数据单元，另一个是存储下一个结点的指针；链表的数据结构实现如下所示：
struct listnode{
int data;
struct listnode next; //c里面必须加上struct，c++里面不需要；当然也可以通过typedef为结构定义一个别名
};
本片文章总结的链表相关题目有：
题目一：求在O（1）时间复杂度内删除改结点？
题目二：链表中结点的个数？
题目三：链表是否存在环？
题目四：查找链表中的倒数第K个结点并返回？
题目五：查找单链表中间结点？
题目六：从尾到头打印链表？
题目七：已知两个结点各自有序，把它们合并成一个有序的链表？
题目八：判断两个链表是否相交？如果相交返回相交的第一个结点？
题目九：一直一个链表存在环，求进入换的第一个结点？
题目十：将链表反转？
下面是问题详解：
题目一：求在O（1）时间复杂度内删除改结点？
这道题乍一看很简单，删除结点找到该节点然后删除不就行了，但是题目要求的是时间复杂度要控制在O（1）内，好像有点困难，但其实也简单，只要用改结点的下一个结点覆盖该结点，然后删除该结点的下一个结点即可；
当然在删除的时候要分两种情况，一种是删除最后一个结点，一种是删除其余结点，删除最后一个结点时因为涉及到最后链表结尾的关系，所以复杂度为O（n），删除其他节点复杂度为O（1）；
void deletenode(listnode *head , listnode *temp){
if(!temp)return ;
if(temp->next){ //删除其他结点
temp->val = temp->next->val;
ListNode * temp = temp->next;
temp->next = temp->next->next;
delete temp;
}
else{ // 要删除的是最后一个节点
if(head == temp){ // 链表中只有一个节点的情况
head = NULL;
delete temp;
}
else{
ListNode * pNode = head;
while(pNode->next != temp) // 找到倒数第二个节点
pNode = pNode->next;
pNode->next = NULL;
delete temp;
}
}
}
题目二：链表中结点的个数？
这道题算是最简单的了，在时间复杂度O（n）内遍历整个链表就可以得到链表的数量；代码参考：
unsigned int getnumoflist(listnode *head){
if(!head)return 0;
listnode* tempnode = head;
if(havecir(tempnode ))
return -1;
else{
unsigned int ret = 0;
while(tempnode){
++ret;
tempnode = tempnode->next;
}
return ret;
}
}
注意，一般很多网上看到的代码会有判断输入是否为NULL的情况；
但是也有一种情况需要注意，就是输入的链表存在环的情况，如果有环不判断的话while会陷入死循环，所以必须提前判断下，在面试的时候提出来应该会好一点，havecir函数会在下面介绍；
题目三：链表是否存在环？
这一题承接上一题，一般判断环的方法是设置快慢指针，快指针一步走两个结点，慢指针一步走一个结点，如果存在环，那么快慢指针必然会在环内某一点相遇，否则没有环就会退出；
bool havecircle(listnode *head){
if(!head) return false;
listnode *pfast = head;
listnode *pslow = head;
while(pfast && pslow){
pfast = pfast->next->next;
pslow = pslow->next;
if(pfast == pslow)
return true;
}
return false;
}
题目四：查找链表中的倒数第K个结点并返回？
解法是设置前后结点，前结点先想向前走k-1步，然后前后结点一块向后走，等前结点到达最后一个结点时，后结点就是倒数第k个结点了；
listnode* findrkthnode(listnode *head , int k){
if(!k || !head) return NULL;
listnode* frontnode = head;
lisenode* backnode = head;
while(k > 1 && frontnode){
--k;
frontnode = frontnode->next;
}
if(k > 1 || !frontnode)
return NULL;
while(frontnode->next){
backnode = backnode->next;
frontnode = frontnode->next;
}
return backnode;
}
题目五：查找单链表中间结点？
跟判断环的时候一样设置快慢指针，当快指针到达结尾的时候，慢指针就是中间结点了；在代码里面我也加了判断是否为环的情况；
listnode* getmidnode(listnode *head){
if(!head || !head->next) return head;
if(havecircle(head)) return NULL;
listnode *pfast = head;
listnode *pslow = head;
while(pfast->next){
pfast = pfast->next;
pslow = pslow->next;
if(pfast->next)
pfast = pfast->next;
}
return pslow;
}
题目六：从尾到头打印链表？
这道题很简单，可以使用递归或者利用栈保存结点并反向直接输出即可；递归算法代码量较少，理解起来相对容易；
递归算法：
void printlist1(listnode *head){
if(!head){
return;
}
else{
printlist(head->next);
printf("%d->" , head->data);
}
}
利用栈的算法：
void printlist2(listnode *head){
stack<int> s;
while(head){
s.push(head->data);
head = head->next;
}
while(!s.empty()){
printf("%d->" , s.top());
s.pop();
}
}
题目七：已知两个结点各自有序，把它们合并成一个有序的链表？
这道题在leetcode上面有，我直接把在上面提交的代码贴出来吧；
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode *result=NULL;
ListNode *temp=NULL;
ListNode *node=NULL;
int fir=1;
while(l1&&l2){
if(l1->val>l2->val){
temp=l2;
l2=l2->next;
}
else{
temp=l1;
l1=l1->next;
}
if(fir){
result=temp;
fir=0;
}
else
node->next=temp;
node=temp;
}
if(l1)
node->next=l1;
if(l2)
node->next=l2;
return result;
}
当然，这道题也有自己的递归算法：
ListNode * mergeTwoLists2(ListNode * head1, ListNode * head2)
{
if(!head1)
return head2;
if(!head2)
return head1;
ListNode * pHeadMerged = NULL;
if(head1->val < head2->val)
{
pHeadMerged = head1;
pHeadMerged->next = mergeTwoLists2(head1->next, head2);
}
else
{
pHeadMerged = head2;
pHeadMerged->next = mergeTwoLists2(head1, head2->next);
}
return pHeadMerged;
}
题目八：判断两个链表是否相交？如果相交返回相交的第一个结点？
首先确定相交，如果两个结点相交那么最后一个结点肯定是公用的，所以只要简单遍历两个链表，然后记住最后一个结点，相比较，如果一样则相交，否则不想交；
bool isintersected(listnode * head1, listnode * head2){
if(!head1 || !head2) return false;
listnode *last1 = head1;
listnode *last2 = head2;
while(last1->next)
last1 = last1->next;
while(last2->next)
last2 = last2->next;
return last1 == last2;
}
默认两个链表确定相交，返回相交的第一个结点，只需要知道两个链表的长度，然后将长链表想前走k步使得其与段链表长度相同，然后同步向下走，若节点相同就返回；
listnode * isintersected(listnode * head1, listnode * head2){
if(!head1 || !head2) return NULL;
int l1 = 0 , l2 = 0 , l;
listnode *tempnode1 = head1;
listnode *tempnode2 = head2;
while(tempnode1->next){
tempnode1 = tempnode1->next;
++l1;
}
while(tempnode2->next){
tempnode2 = tempnode2->next;
++l2;
}
tempnode1 = head1;
tempnode2 = head2;
if(l1 > l2){
l = l1 - l2;
while(l > 0){
tempnode1 = tempnode1->next;
--l;
}
}
else if(l2 > l1){
l = l2 - l1;
while(l > 0){
tempnode2 = tempnode2->next;
--l;
}
}
while(tempnode1->val != tempnode2->val){
tempnode1 = tempnode1->next;
tempnode2 = tempnode2->next;
}
return tempnode;
}
题目九：一个链表存在环，求进入换的第一个结点？
首先找到链表中的任一结点，然后将其下一结点指向NULL，这样就可以转化为求两个相交链表相交的第一个结点的问题了；
listnode* GetFirstNodeInCircle(listnode * pHead)
{
if(!pHead || !pHead->next)
return NULL; listnode * pFast = pHead;
listnode * pSlow = pHead;
while(pFast && pFast->next)
{
pSlow = pSlow->next;
pFast = pFast->next->next;
if(pSlow == pFast)
break;
}
if(!pFast || !pFast->next)
return NULL; // 将环中的此节点作为假设的尾节点，将它变成两个单链表相交问题
listnode * pAssumedTail = pSlow;
listnode * pHead1 = pHead;
listnode * head = pAssumedTail->next; int l1 = 0 , l2 = 0 , l;
listnode *tempnode1 = pHead1;
listnode *tempnode2 = head; while(tempnode1->next){
tempnode1 = tempnode1->next;
++l1;
}
while(tempnode2->next){
tempnode2 = tempnode2->next;
++l2;
}
tempnode1 = pHead1;
tempnode2 = head;
if(l1 > l2){
l = l1 - l2;
while(l > 0){
tempnode1 = tempnode1->next;
--l;
}
}
else if(l2 > l1){
l = l2 - l1;
while(l > 0){
tempnode2 = tempnode2->next;
--l;
}
}
while(tempnode1->val != tempnode2->val){
tempnode1 = tempnode1->next;
tempnode2 = tempnode2->next;
}
return tempnode;
}
题目三：将链表反转？
存在两种解法，一种是利用循环，一种是利用递归，通常情况下推荐使用循环，因为递归太深容易造成堆栈的溢出，并且调用函数要消耗资源，所以递归空间和时间消耗都大；
循环解法：从头到尾循环一个一个遍历结点，逆序链表；
listnode *reverselist1(listnode *head){
if(!head || !head->next) return head;
listnode *retnode = NULL; //反转后的新链表头指针，
listnode *pCurrent = phead;
listnode *ptemp = NULL;
while(pCurrent){
ptemp = pCurrent;
pCurrent = pCurrent->next;
ptemp->next = retnode;
retnode = ptemp;
}
return retnode;
}
递归解法：递归到链表的结尾，然后返回时逆序链表；
listnode *reverselist2(listnode *head){
if(!head)return NULL;
listnode *tempnode = head;
if(head && head->next){
listnode *retnode = reverse(head);
tempnode = NULL;
}
return retnode;
}
listnode *reverse(listnode *head){
listnode *retnode = NULL;
if(head)
retnode = reverselist2(head->next);
if(head && head->next){
if(!retnode)
retnode = head->next;
head->next = head;
}
return retnode;
}