数据结构链表习题

第一题单链表如何逆置//方法一借助辅助结点 void Reverse1(Node* plist) { //0.最少两个节点才逆置、 if (Get_length(plist) 2) return; //1.申请两个指针p和q,p初始化指向第一个有效节点q初始化指向第二个有效结点 Node* p plist-next; Node* q p-next; //2.将第一个结点的next置为NULL plist-next NULL; //3.进入while循环循环条件是p指向的节点得存在 while (p ! NULL) { q p-next; //4.将p指向节点头插到plist链表里 p-next plist-next; plist-next p; //5.再让p同步到q的位置 p q; } } //方法二不借助辅助节点 void Reverse2(Node* plist){ //0.最少两个节点才逆置 if (Get_length(plist) 2) return; //1.申请3个指针p和q和r,p初始化指向第一个有效节点q初始化指向第二个有效结点r初始化NULL Node* p plist-next; Node* q p-next; Node* r NULL; //将第一个结点的next置为NULL p-next NULL; //2.进入while循环循环条件是q指向的节点得存在 while(q!NULL) { //3.通过三个指针p q r相互配合将p和q之间的箭头逆置 r q-next; q-next p; p q; q r; } //4.当while循环结束说明3个指针pqr此时已经将所有指针逆置辅助结点的next保存此时p的地址 plist-next p; }第二题找到单链表倒数第K个节点intGet_k_backwards(Node*plist,intk){assert(plist!NULL);assert(k1kGet_length(plist));//方法1/*int pos Get_length(plist) - k 1; for (int i 0; i pos; i) plist plist-next; return plist-data ;*///方法2Node*pplist;Node*qplist;for(inti0;ik;i)pp-next;while(p!NULL){pp-next;qq-next;}returnq-data;}第三题(1)判断有没有相交点boolIntersect1(Node*plist1,Node*plist2){assert(plist1!NULL);assert(plist2!NULL);Node*pplist1;Node*qplist2;for(;p-next!NULL;pp-next);for(;q-next!NULL;qq-next);returnpq;}(2)如果相交返回第一个相交点如果不相交返回空地址Node* Intersect2(Node* plist1, Node* plist2) { assert(plist1 ! NULL); assert(plist2 ! NULL); int len1 Get_length(plist1); int len2 Get_length(plist2); //默认让P1指向较长的 Node* p1 (len1 len2) ? plist1 : plist2; Node* p2 (len1 len2) ? plist2 : plist1; for (int i 0; i abs(len1 - len2); i) { p1 p1-next; } //代码执行到这里P1 P2距离尾节点的长度相同 while (p1 ! p2) { p1 p1-next; p2 p2-next; } //不相交即相交点就是走到NULL返回空地址 return p1; }第四题任意删除一个结点boolDel_Node(Node*p){assert(p!NULL);//1.防止其是尾节点if(p-nextNULL)returnfalse;//2.既然不是尾节点,则要找到该节点的下一个结点替死鬼用指针指向Node*qp-next;//3.将下家数据拷贝给我当前的节点的数据域p-dataq-data;p-nextq-next;free(q);qNULL;returntrue;}第五题判断是否是回文链表boolPalindrome(Node*plist){assert(plist!NULL);intlenGet_length(plist);int*arr1(int*)malloc(len*sizeof(int));int*arr2(int*)malloc(len*sizeof(int));for(Node*pplist-next,inti0;p!NULL;pp-next,i){arr1[i]p-data;arr2[len-i-1]p-data;}for(inti0;ilen;i){if(arr1[i]arr2[i]){returntrue;}}}第六题判断是否有环 有环直接返回入环点没有环返回空指针//快慢指针快指针一次两步 慢指针一次一步Node*Is_Circle(Node*plist){//0.断言assert(plist!NULL);assert(plist-next!NULL);//最少有一个元素才能形成环//1.申请两个指针快慢指针让其默认都指向辅助节点头结点Node*quickplist;Node*slowplist;//2.让快慢指针各自先动一次慢动1 快动2slowslow-next;quickquick-next-next;//3.进入while循环循环条件是在快指针遇到NULL之前看快慢指针是否能再次相遇while(quick!NULLquick!slow){slowslow-next;quickquick-next;//一次走两步 有风险 因为有可能第一步踏空if(quick!NULL)quickquick-next;}//4.while循环结束有两种情况情况一quickNULL没有环 情况二quickNULL但quickslow 说明有环if(quickNULL)returnNULL;//找入环点的方法//1.申请一个指针P从头结点出发Node*pplist;//2.再申请一个指针q从快慢指针相遇点出发Node*qquick;//3.让他俩同一时间保存同样的速度出发当他俩相遇时相遇点就是入环点while(p!q){pp-next;qq-next;}returnp;}