往期链表文章:(如果想更多的了解单链表,笔者建议可以简略的了解往前的文章)
创建链表、打印链表、释放内存的基础操作这里就不code了，想了解的朋友可以浏览
今日份试题1：
题目描述：给定一个单链表的头节点head,请判断该链表是否为回文结构。
实现思路1：栈方法（额外空间复杂度O(N)）
我们先聊下栈的特点：先进先出
abcd依次入栈，得到的出栈序列：dcba （逆序）
对于判断回文，我们也可以先将其压入栈，然后逐个弹出与原来的序列进行比较。
bool isPalidrome1(Node head){ if(head==NULL){ return true; //空串我们这里算回文串 } stack<node> sta; Node cur = head; //依次压入栈 while(cur!=NULL){ sta.push(*cur); cur = cur->next; } //比较 while(head != NULL){ if(head->value != sta.top().value){ return false; } sta.pop(); head = head->next; } return true; }
做个简单优化：其实只需要将一半的序列压入栈中就可以了，节省空间的开销。
先通过快慢指针左预处理找到中点位置，奇数长度返回中点，偶数长度返回下中点。
bool isPalidrom2(Node head){ //如果为空 if(head == NULL){ return true; } //如果只有一个结点 if(head->next == NULL){ return true; } stack<node> sta; Node slow = head->next; Node fast = head->next; while(fast != NULL && fast->next != NULL){ fast = fast->next->next; slow = slow->next; }//slow指向的就是中点 while(slow != NULL){ sta.push(*slow); slow=slow->next; } while(!sta.empty()){ if(head->value != sta.top().value){ return false; } head = head->next; sta.pop(); } return true; }
实现思路2：改变链表法
先通过快慢指针找到中点，然后改变中点以后的结点的next指向，使其指向反方向。然后一个从头部一个从尾部开始，比较是否相等，判断是不是回文串。最后将链表的链表还原
【我去，这样太复杂了吧。没办法单链表只有一个指向后继结点的指针】
bool isPalidrome3(Node head){ if(head == NULL){ return true; } if(head->next == NULL){ return true; } Node slow = head; Node fast = head; while (fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; } Node n2 = fast; Node n1 = slow; n2 = n1->next; n1->next = NULL; Node n3 = NULL; while (n2 != NULL) { n3 = n2->next; n2->next = n1; n1 = n2; n2 = n3; } n3 = n1; n2 = head; bool res = true; while (n1 != NULL && n2 !=NULL){ if(n1->value != n2->value){ res = false; break; } n1 = n1->next; n2 = n2->next; } n1 = n3->next; n3->next = NULL; while (n1 != NULL) { n2 = n1->next; n1->next = n3; n3 = n1; n1 = n2; } return res; }
今日份试题2：
问题描述：将单向链表按值划分成左边小、中间相等、右边大的形式
实现思路1：把链表放入数组里，在数组上做partition
//将单个链表按某值划分成左边小、中间相等、右边达的形式 //code1-->把链表放入数组里,在数组上做化分 空间复杂度O(n) void arrPartition(Node arr,int len,int pivot){ int less = -1; //-1表示没有比pivot小的数 int more = len; //len表示没有比pivot大的数 int L = 0; //通过L来遍历数组 //分三种情况 arr[L]<pivot arr[L]>pivot arr[L]==povit while(L < more){ if(arr[L].value < pivot){ swap(arr[++less],arr[L++]); }else if(arr[L].value > pivot){ swap(arr[L],arr[--more]); }else{ L++; } } } Node listPartition1(Node head, int pivot){ if(head == NULL){ return head; } Node cur = head; int len = 0; //单链表的长度 int i = 0; //计算单链表的长度 while(cur != NULL){ len++; cur = cur->next; } cout<<"length:"<<len<<endl; //计算len的作用体现出来了,因为要在堆上分配内存 //如果我们没有指定len,那么编译器将无法直到要给我们多大的空间 //如果你所可以分配一个很大的空间，但剩余的空间将会被浪费掉 Node nodeArr= new node[len]; cur = head; //将单链表中的值依次放入数组中 for(int i=0;i<len;i++){ nodeArr[i] = *cur; cur = cur->next; // cout<<"--->"<<nodeArr[i].value<<endl; } //在数组上做划分 arrPartition(nodeArr,len,pivot); //这里有两种处理方法 /*1.以这个数组重新制作一个链表 2.将这个数组中的值去覆盖原来链表中的值 */ //code1: // for(int i=1;i<len;i++){ // nodeArr[i-1].next = &nodeArr[i]; // } // nodeArr[i].next = NULL; // delList(head); // return nodeArr; //code2: cur = head; for(int i=0;i<len;i++){ cur->value=nodeArr[i].value; cur=cur->next; } delete nodeArr; //别忘了释放堆上的空间 return head; }
实现思路2：分成小、中、大三部分，再把各个部分之间串起来。
//将单个链表按某值划分成左边小、中间相等、右边达的形式 //code2-->通过6个状态指针来将原来的链表分成三个链表 /*小于pivot 等于pivot 大于pivot*/ Node listPartition2(Node head,int pivot){ Node sH = NULL; //保存小于链表的头部 Node sT = NULL; //保存大于链表的尾部 Node eH = NULL; //保存等于链表的头部 Node eT = NULL; //保存等于链表的尾部 Node mH = NULL; //保存大于链表的头部 Node mT = NULL; //保存大于链表的尾部 Node next = NULL; //保持下一个结点,很关键的 while(head != NULL){ next = head->next; //将限一个结点通过next先保存下来 head->next = NULL; //arr[L] < pivot if(head->value < pivot){ if(sH == NULL){ //当小链表没有结点的时候 sH = head; sT = head; }else{ sT->next = head; sT = head; } }else if(head->value > pivot){ if(mH == NULL){ mH = head; mT = head; }else{ mT->next = head; mT = head; } }else{ if(eH == NULL){ eH = head; eT = head; }else{ eT->next = head; eT = head; } } head = next; } //将三个链表连接起来 /*将小于区的尾部连接到等于区的头部*/ //如果有小于区才能连 if(sT != NULL){ sT->next = eH; //如果没有等于区就将等于区的尾部合并小于区 eT = eT==NULL?sT:eT; } //将小于等于区的尾部连接在大于区 if(eT != NULL){ //eT==NULL:既没有小于区也没有大于区 eT->next = mH; } sH = sH!=NULL ? sH:(sH!=NULL?eH:mH); return sH; }
今日份试题3：
一种特殊的单链表结点描述如下
class Node{ int value; Node next; Node rand; Node(int val){value=val;} }
rand指针是单链表结构中新增的指针，rand可能指向链表中的任意一个结点，也可能指向NULL。
给定一个由Node结点类型组成的无环单链表的头节点head,请实现一个方法来完成这个链表的复制，并返回新链表。
解题思路1：通过哈希表映射，来保持父节点（被拷贝的那个）和子结点（复制的）之间的对应关系。
Node copyListWithRand1(Node head){ unordered_map<Node,Node> map; Node cur = head; while(cur != NULL){ map.insert(pair<Node,Node>(cur,new node(cur->value))); cur = cur->next; } cur = head; while (cur != NULL) { map[cur]->next = map[cur->next]; map[cur]->rand = map[cur->rand]; cur = cur->next; } Node tmp = map[head]; return tmp; }
解题思路2：
将新结点先挂在原先结点的下一个结点(如此以来便可以找到原结点所对应的复制结点)
然后拷贝rand的指向
分离-->拷贝后的结点和原结点
Node copyListWithRand2(Node head){ if(head == NULL){ return head; } //创建新结点并挂原先结点上 Node next = NULL; Node cur = head; while(cur != NULL){ next = cur->next; cur->next = new node(cur->value); cur->next->next = next; cur = next; } //拷贝rand结点 Node curCopy = NULL; cur = head; next = NULL; while(cur != NULL){ next = cur->next->next; curCopy = cur->next; curCopy->rand = cur->rand!=NULL ? cur->rand->next : NULL; cur = next; } // //分离 cur = head; Node res = cur->next; next = NULL; while(cur != NULL){ next = cur->next->next; curCopy = cur->next; cur->next = next; curCopy->next = next!=NULL ? next->next:NULL; cur = next; } return res; }
其它辅助代码：
#include <iostream> #include <cstdlib> #include <unordered_map> //c++????? using namespace std; struct node { public: int value; node *next; node *rand; node(int data){this->value = data;this->next=NULL;this->rand=NULL;}; ~node(){}; }; typedef node* Node; // Node init(){ //???????? Node head = NULL; Node next = NULL; //Node cur = NULL; head = new node(1); next = new node(2); head->next = next; next->rand = head; next = new node(3); head->next->next = next; head->rand = next; return head; } // void printList(Node head){ if(head == NULL){ return; } Node cur = head; while(cur != NULL){ cout<<cur->value<<" "<<endl; cur = cur->next; } } //释放 void delList(Node head){ if(head == NULL){ return; } Node p = head->next; while(p!=NULL){ if(p->rand != NULL){ p->rand = NULL; } delete head; head = p; p = p->next; } delete head; head = NULL; }
int main() { Node head = NULL; Node pre = NULL; //初始化 head = init(); // pre = copyListWithRand1(head); pre = copyListWithRand2(head); cout<<"head-->"<<endl; printList(head); cout<<endl; cout<<"pre-->"<<endl; printList(pre); cout<<endl; delList(head); delList(pre); system("pause"); return 0; }
