接上一篇单链表的基本操作，我又整理了一些链表常考的题目，并且不断更新中。。。 1.查找链表中倒数第k个节点以及删除倒数第k个节点
//给两个指针p和q，让其中一个指针p领先q指针k步，，//然后再同时移动p和q指针，当领先的指针p先到达链表尾部时，后面的指针q所指向的节点恰好为倒数第k个节点。Node* GetKthNode(int k){Node *p=head;Node *q=head;p->next!=NULL){p=p->next;k–;}p==NULL)return NULL;while(p->next!=NULL){q=q->next;p=p->next;}return q;}//删除倒数第k个节点Node* DelKthNode(int k){Node *p=head;Node *q=head;p->next!=NULL){p=p->next;k–;}p==NULL)return NULL;Node ){pre=q;q=q->next;p=p->next;}pre->next=q->next;return head;}
2.求链表的中间节点
//给定两个指针p和q,让p指针走两步，同时q指针走一步。当p指针指向尾处或者尾处前一个结点时，中间值求得//若链表长度为奇数，q所在节点即为中间节点；若链表长度为偶数，q所在节点即为中间两个节点的前一个（这里我们就让其返回前一个节点）。int getMid(){head->next==NULL)return 0;if(head->next->next==NULL)return head->data;Node *p=head;Node *q=head;p->next->next!=NULL){p=p->next->next;q=q->next;}return q->data;}
3.在o(1)的时间复杂度删除单链表中指定的某一节点
delNode(Node *head,Node *toDelete){if(head==NULL)return;if(head->next==NULL)head=NULL;else{if(toDelete->next!=NULL)//要删除的不是尾节点{toDeletetoDelete->next->data;toDelete->next=toDelete->next->next;}else{Node *node=head;while(node->next!=toDelete)node=node->next;node->next=NULL;}}}
4.从尾到头打印单链表
//从尾到头打印节点void reversePrintLink(){if(head==NULL)return;stack<int> s;Node* p=head;while(p!=NULL){s.push(p->data);p=p->next;}int value=0;while(!s.empty()){value = s.top();//不能直接用pop()赋值,pop返回的是void类型s.pop();cout<<value<<” “;}cout<<endl;}
有时我们选择改变，并非经过深思熟虑，而更像是听见了天地间冥冥中的呼唤，
