# 单链表

2023-09-08

#### 单链表结构定义

typedef struct LNode {
ElemType data; 	//节点数据域
struct LNode *next;	//节点指针域

LNode *p;   //定义节点指针


#### 初始化

void initList(LinkList &L)
{
L->next = NULL;
}


### 单链表基本操作

#### 头插法建立单链表

LinkList list_HeadInsert() {
LNode *p;
int x;
L->next = NULL;
scanf("%d", &x);
while(x != 9999) {
p = (LNode*)malloc(sizeof(LNode));
p->data = x;
p->next = L->next;
L->next = p;
scanf("%d", &x);
}
return L;
}


#### 尾插法建立单链表

LinkList list_TailInsert() {
LNode *p, *r;
int x;
L->next = NULL;
r = L;
scanf("%d", &x);
while(x != 9999) {
p = (LNode *)malloc(sizeof(LNode));
p -> data = x;
r -> next = p;
r = p;
scanf("%d", &x);
}
r -> next = NULL;
return L;
}


#### 单链表查找

//按序号查找
LNode *getElem(LinkList L, int i) {
if (i < 1)	return NULL;
int j = 1;
LNode *p = L -> next;
while(p != NULL && j < i) {
p = p -> next;
j ++;
}
return p;
}

//按值查找
LNode *locateElem(LinkList L, int x) {
LNode *p = L -> next;
while(p != NULL && p->data != x) {
p = p -> next;
}
return p;
}


#### 单链表插入

void insertNode(LinkList &L, LNode *s, int pos) {
LNode *pre = getElem(L, pos - 1);
s -> next = pre -> next;
pre -> next = s;
}


#### 单链表删除

void deleteNode(LinkList &L, int pos) {
LNode *pre = getElem(L, pos - 1);
LNode *q = pre -> next;
pre->next = q->next;
free(q);
}


#### 单链表表长

int getLength(LinkList L) {
int cnt = 0;
for (LNode *p = L -> next; p != NULL; p = p -> next) {
cnt ++;
}
return cnt;
}


### 单链表相关题目

void del(LinkList &L, int x) {
LNode *p;
if (L == NULL) {
return ;
}
if (L -> data == x) {
p = L;
L = L -> next;
free(p);
del(L, x);
} else {
del(L -> next, x);
}
}


void delNum(LinkList &L, int x) {
LNode *p = L -> next, *pre = L, *q;
while(p != NULL) {
if (p -> data == x ) {
q = p;
p = p -> next;
pre -> next = p;
free(q);
} else {
pre = p;
p = p -> next;
}
}
}


void rev_Print(LinkList L) {
if (L -> next != NULL) {
rev_Print(L->next);
}
if (L != NULL)
printf("%d ", L->data);
}


void del_Min(LinkList &L) {
LNode *pre = L, *p = pre -> next;
LNode *minpre = pre, *minp = p;
while(p != NULL) {
if (p -> data < minp -> data) {
minp = p;
minpre = pre;
}
pre = p;
p = p -> next;
}
minpre -> next = minp -> next;
free(minp);
}


void list_Reverse(LinkList &L) {
LNode *p, *r;
p = L -> next;
L -> next = NULL;
while(p != NULL) {
r = p -> next;  //保留后面结点
p -> next = L -> next;
L -> next = p;
p = r;	//恢复后续
}
}


void insertSort(LinkList &L) {
LNode *p = L -> next, *pre;
LNode *r = p -> next;	//保存p的后继指针，不断链
p -> next = NULL;	//初始化只保留一个数据结点
p = r;
while(p != NULL) {
r = p -> next;
pre = L;	// 每次进行插入排序，pre重置头结点
while(pre->next != NULL && pre->next->data < p->data) {
pre = pre -> next;
}
p -> next = pre -> next;
pre -> next = p;
p = r;
}
}


void rangeDel(LinkList &L, int min, int max) {
LNode *pre = L, *p = L -> next;
while(p != NULL) {
if (p -> data > min && p -> data < max) {
pre -> next = p -> next;
free(p);
p = pre -> next;
} else {
pre = p;
p = p -> next;
}
}
}


LinkList searchCommon(LinkList L1, LinkList L2) {
int len1 = getLength(L1);
int len2 = getLength(L2);
int lenDis = abs(len1 - len2);
if (len1 > len2) {
longList = L1 -> next;
shortList = L2 -> next;
} else {
shortList = L2 -> next;
longList = L1 -> next;
}
while(lenDis --)
longList = longList -> next;
while(longList != NULL) {
if (longList == shortList)
return longList;
else {
longList = longList -> next;
shortList = shortList -> next;
}
}
return NULL;
}


void min_Del(LinkList &L) {
while(L -> next != NULL) {	//循环到只剩头结点
LNode *pre = L;		//pre为元素最小值结点的前驱结点指针
LNode *p = pre -> next;	//	工作指针
LNode *q;	//指向被删除指针
while(p -> next != NULL) {	//找到最小值的前驱
if (p -> next -> data < pre -> next -> data)
pre = p;
p = p -> next;
}
printf("%d ", pre -> next -> data);
q = pre -> next;
pre -> next = q -> next;	//删除最小值
free(q);
}
free(L);
}


LinkList discreat(LinkList &A) {
int i = 0;
B -> next = NULL;
LNode *ra = A, *rb = B, *p;

p = A -> next;
A -> next = NULL;
while(p != NULL) {
i ++;
if (i % 2 == 0) {
rb -> next = p;
rb = p;
} else {
ra -> next = p;
ra = p;
}
p = p -> next;
}
ra -> next = NULL;
rb -> next = NULL;
return B;
}


$C=a_1,b_1,a_2,b_2...a_n,b_n$为线性表，采用带头结点单链表存储，设计一个就地算法，将其拆分为两个线性表，使得$A=a_1,a_2...a_n$,$B=b_n,b_{n-1}...b_1$

LinkList discreat2(LinkList &A) {
B -> next = NULL;
LNode *p = A -> next, *q;
LNode *ra = A;
while(p != NULL) {
ra -> next = p;
ra = p;
p = p -> next;
if (p != NULL) {
q = p -> next;
p -> next = B -> next;
B -> next = p;
p = q;
}
}
ra -> next = NULL;
return B;
}


void delSame(LinkList &L) {
LNode *p = L -> next, *q;
if (p == NULL)	return ;
while(p -> next != NULL) {
q = p -> next;
if (p -> data == q -> data) {
p -> next = q -> next;
free(q);
} else {
p = p -> next;
}
}
}


void MergeList(LinkList &A, LinkList &B) {
LNode *pa = A -> next, *pb = B -> next, *q;
A -> next = NULL;

while(pa && pb) {
if (pa -> data <= pb -> data) {
q = pa -> next;
pa -> next = A -> next;
A -> next = pa;
pa = q;
} else {
q = pb -> next;
pb -> next = A -> next;
A -> next = pb;
pb = q;
}
}
if (pa)	//处理非空链表
pb = pa;
while(pb) {
q = pb -> next;
pb -> next = A -> next;
A -> next = pb;
pb = q;
}
free(B);
}


LinkList getCommon(LinkList A, LinkList B) {
LNode *pa = A -> next, *pb = B -> next, *r, *s;
C -> next = NULL;
r = C;
while(pa && pb) {
if (pa -> data < pb -> data) {
pa = pa -> next;
} else if (pa -> data > pb -> data) {
pb = pb -> next;
} else {
s = (LNode*)malloc(sizeof(LNode));
s -> data = pa -> data;
r -> next = s;
r = s;
pa = pa -> next;
pb = pb -> next;
}
}
r -> next = NULL;
return C;
}


void unionList(LinkList &A, LinkList &B) {
LNode *pa = A -> next, *pb = B -> next;
LNode *r = A, *u;

while(pa && pb) {
if (pa -> data < pb -> data) {
u = pa;
pa = pa -> next;
free(u);
} else if (pa -> data > pb -> data) {
u = pb;
pb = pb -> next;
free(u);
} else {
r -> next = pa;
r = pa;
pa = pa -> next;
u = pb;
pb = pb -> next;
free(u);
}
}
while(pa) {
u = pa;
pa = pa -> next;
free(u);
}
while(pb) {
u = pb;
pb = pb -> next;
free(u);
}
r -> next = NULL;
free(B);
}


bool judge(LinkList A, LinkList B) {
LNode *pa = A -> next, *pb = B -> next;
LNode *pre = pa;

while(pa && pb) {
if (pa -> data == pb -> data) {
pa = pa -> next;
pb = pb -> next;
} else {
pre = pre -> next;
pa = pre;
pb = B -> next;
}
}
return pb == NULL ? true : false;
}


LNode *findLoop(LNode *L) {
LNode *fast = L -> next, *slow = L -> next;
while(fast != NULL && fast -> next != NULL) {
slow = slow -> next;
fast = fast -> next -> next;
if (slow == fast)
break;
}
if (fast == NULL || fast -> next == NULL)
return NULL;
LNode *p1 = L -> next;
LNode *p2 = slow;
while(p1 != p2) {
p1 = p1 -> next;
p2 = p2 -> next;
}
return p1;	//入口点
}


int searchK(LinkList list, int k) {
LNode *p = list -> next;
LNode *q = list -> next;
int cnt = 0;
while (p != NULL) {
if (cnt < k)	cnt ++;
else	q = q -> next;
p = p -> next;
}
if (cnt < k)	return 0;	//k比链表长度还长，不合法
else {
printf("%d\n", q -> data);
return 1;
}
}


LNode* find_addr(LinkList str1, LinkList str2) {
int m = getLength(str1);
int n = getLength(str2);
LNode *p, *q;
for (p = str1; m > n; m --)
p = p -> next;
for (q = str2; n > m; n --)
q = q -> next;
while(p -> next != NULL && p -> next != q -> next) {
p = p -> next;
q = q -> next;
}
return p -> next;
}


void delAbs(LinkList &L, int n) {
LNode *p = L, *r;
int *vis = (int *)malloc(sizeof(int)*(n + 1));
for (int i = 0; i < n + 1; i ++)
*(vis + i) = 0;
while(p -> next != NULL) {
int m = p -> next -> data > 0 ? p -> next -> data : -p -> next -> data;
if (*(vis + m) == 0) {
*(vis + m) = 1;
p = p -> next;
} else {
r = p -> next;
p -> next = r -> next;
free(r);
}
}
}


$L=a_1,a_2,a_3,...a_{n-2},a_{n-1},a_{n}$为线性表，采用带头结点单链表存储，设计算法，将其变为$L=a_1,a_n,a_2,a_{n-1},a_3,a_{n-2}...$

void changeList(LinkList &L) {
LNode *p, *q, *r, *s;
p = q = L;
while(q -> next != NULL) {	//寻找中间结点
p = p -> next;
q = q -> next;
if (q -> next != NULL)
q = q -> next;
}
q = p -> next;	//此时p所指向中间结点
p -> next = NULL;	//断开分成两段
while(q != NULL) {	//	后半段逆置
r = q -> next;
q -> next = p -> next;
p -> next = q;
q = r;
}
s = L -> next;	//指向前半段第一个
q = p -> next;	//指向后半段第一个
p -> next = NULL;
while(q != NULL) {	//将链表后半段的结点插入到指定位置，前插法
r = q -> next;
q -> next = s -> next;
s -> next = q;
s = q -> next;
q = r;
}
}


Q.E.D.