#include<iostream>
#include"LinkList.h"
/*
算法思想：i是记节点个数的，s和p初始指向第一个节点，i=1，
然后p会逐渐遍历节点，直到遍历完所有节点或i=k为止。
若循环结束时P=NULL则k不合法。
若循环结时i=k则，从s开始到p，正好k个节点。
s和p都遍历下去，直到p是尾节点，s就是倒数k节点
整个算法时间复杂度为O(1)
*/
Status exercise1(LinkList L, int k) {
if (k < 1) return ERROR; //不合法
LNode * p = L->next;
LNode * s = L->next;
int i = 1;
while (p != NULL && i != k) {
p = p->next;
i++;
}
if (p == NULL) return ERROR; //没有k个节点 不合法
while (p->next != NULL) {//p是最后一个节点时，s所在的节点就是倒数k
p = p->next;
s = s->next;
}
cout << s->data << endl;
return OK;
}
/*
基本思想：寻找s为指向长链表中的一个节点，使得s之后的节点数与短链表节点数相同。
然后长链表从s开始，短链表从第一个节点开始比较两个链表同位置节点是否为一个节点就好了。
寻找s的方法：p1=str1,p2=str2,p1p2同时遍历直到一个链表到达尾节点，此链表为短链表。s=长链表头节点。
s与长链表p一起遍历直到p到达尾节点。此时s就是我们想要的。
整个算法时间复杂度为O(1)
*/
LNode* exercise2(LinkList str1, LinkList str2) {
LNode* p1 = str1, * p2 = str2, * s = NULL, * q1 = NULL, * q2 = NULL;
//说明：p1，p2遍历两个链表，q1,q2分别为长链表和短链表中的节点
while (p1->next != NULL && p2->next != NULL) {
p1 = p1->next;
p2 = p2->next;
}
if (p1->next == NULL){ //str1是短链表
q1 = p2;
s = str2->next;
q2 = str1->next;
}
else { //str2是短链表
q1 = p1;
s = str1->next;
q2 = str2->next;
}
while (q1->next != NULL) {
s = s->next;
q1 = q1->next;
}
while (s != NULL) {
if (s == q2) {
return s;
}
s = s->next;
q2 = q2->next;
}
return NULL;//没有共同节点返回NULL
}
/*
题目明显提示|data|<n。所以使用辅助数组，a[n]=0。
遍历链表，若a[|data|]=0则a[|data|]++，若a[|data|]=1则删除该节点
时间复杂度为O(m)空间复杂第为O(n)
*/
#define N 100
Status exercise3(LinkList head) {
int a[N] = {0};
LNode* s = head->next;
LNode* p = head;
while (s != NULL) {
if (a[abs(s->data)] == 0) {
a[abs(s->data)]++;
p = s;
s = s->next;
}
else {
p->next = s->next;
free(s);
s = p->next;
}
}
return OK;
}
/*
简单的方法，看代码就好了。需要三个指针。
时间复杂度为O(n)
*/
Status exercise4(LinkList L) {
LNode* p=NULL , *r=NULL, *l=NULL;
l = L->next;
if (l) p = l->next;
l->next = NULL; //第一个节点reverse后为最后一个节点
while (p != NULL) {
r = p->next;
p->next = l;
l = p;
p = r;
}
L->next = l; //l是尾节点，换为第一个节点
return OK;
}
/*
基本思想：找到中间节点，将后面的节点原地逆置，然后逐步修改链子
*/
Status exercise5(LinkList L) {
LNode* p1 = L;
LNode* p2 = L;
LNode* s1 = NULL;
LNode* s2 = NULL;
LNode* s = NULL;
while (p1 != NULL && p1->next != NULL) {
p1 = p1->next;
p1 = p1->next;
p2 = p2->next;
}//结束后
exercise4(p2);//p2后面的节点会被逆置
s = p2; //记录中点
p1 = L->next;
p2 = p2->next;
//此时p1指向第一个节点，p2指向逆置后d额部分的第一个节点
while (p2 !=NULL) {//p1遍历未逆置的节点，p2遍历逆置后的节点
s1 = p1->next;
s2 = p2->next;
p1->next = p2;
p2->next = s1;
if (s2 == NULL) {//循环就要结束了
if (s1 == s) {//链表单数
s1->next = NULL;
}
else { //链表双数
p2->next = NULL;
}
}
p1 = s1;
p2 = s2;
}
return OK;
}
/*
构造出符合题目要求的链表来验证我们的答案甚至比解题都难!
*/
int main() {
Status List_TailInsert(LinkList & L);
Status ListPrint(LinkList L);
LinkList L = NULL;
cout << "请输入链表" << endl;
List_TailInsert(L);
cout << "exercise5:" << endl;
exercise5(L);
ListPrint(L);
/* LinkList L = NULL;
cout << "请输入链表" << endl;
List_TailInsert(L);
cout << "原始L:" << endl;
ListPrint(L);
cout << "exercise4:" << endl;
exercise4(L);
ListPrint(L);
*/
/*
* exercise3
LinkList head = NULL;
cout << "请输入链表:" << endl;
List_TailInsert(head);
cout << "excise3:" << endl;
exercise3(head);
ListPrint(head);
*/
/*
exercise2
LinkList str1=NULL,str2=NULL,str3 = NULL,p;
cout << "请输入第一个链表" << endl;
List_TailInsert(str1);//用数字代替题中的字母
cout << "请输入第二个链表" << endl;
List_TailInsert(str2);//用数字代替题中的字母
cout << "请输入第三个链表" << endl;
List_TailInsert(str3);//用数字代替题中的字母
p = str1;
while (p->next != NULL) {
p = p->next;
}
p->next = str3->next;
p = str2;
while (p->next != NULL) {
p = p->next;
}
p->next = str3->next;
cout << "str1:" << endl;
ListPrint(str1);
cout << "str2:" << endl;
ListPrint(str2);
cout << "共同元素是" << endl;
LNode* x = exercise2(str1, str2);
if (x != NULL) {
cout << x->data;
cout << "\t";
ListPrint(x);
}
else cout << "NULL" << endl;
*/
/*exercise1
* LinkList L;
int k;
cout << "尾插法建立链表" << endl;
List_TailInsert(L);
cout << "请输入，寻找倒数第k个节点，k值：" << endl;
cin >> k;
cout << "值为：" << endl;
cout << exercise1(L, k) << endl;
*/
}
评论0