单链表

单链表的结构示意图

  单链表是一种顺序存储的结构. 有一个头结点,没有数据,只存储链表第一个节点的地址. 除了尾结点,每个节点都有唯一的直接后继. 所以,单链表中查询第i个元素必须知道头结点且顺序访问前i-1个结点数据才能找到.

单链表统一结构

1
2
3
4
5
typedef int ElementType;
typedef struct Node{
ElementType data;
struct Node* next;
}*ListNode;

查找单链表中倒数第k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* findKth(ListNode* head, int k){
if(head == NULL || k == 0) //倒数第0个无意义
return NULL;

ListNode* p = head;
ListNode* q = head;
for(int i = 0;i < k - 1; i++){ //先让第一个指针走到第k个结点,如果链表不够长,直接返回空
if(p->next != NULL)
p = p->next;
else
return NULL;
}

while(p->next != NULL){ //p只要走到结尾,q即为倒数第k个结点
p = p->next;
q = q->next;
}

return p;
}

合并两个有序的单链表,合并后依然有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
ListNode* Merge(ListNode* p, ListNode* q){	//采用归并的思想
if(!p) return q;
if(!q) return p; //若有一个为空,返回另一个

ListNode *r = NULL;
ListNode *rhead = NULL;
if(p->data < q->data){ //定下头指针
rhead = p;
p = p->next;
}
else{
rhead = q;
q = q->next;
}
r = rhead; //r当工作指针
while(p!=NULL && q!=NULL){ //公共部分进行有序合并
if(p->data < q->data){
r->next = p;
p = p->next;
else{
r->next = q;
q = q->next;
}
r = r->next;
}

if(p == NULL) r->next = q; //公共部分跳出后,若有剩下,则直接指向剩下的头
if(q == NULL) r->next = p;

return rhead;
}

单链表的就地逆置(头插法)

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* p){
ListNode* q = p;
ListNode* qpre = NULL;
while(q != NULL){
ListNode *r = q->next; //防止断链
q->next = qpre; //保存尾指针
qpre = q; //完成一次翻转,前移
q = r;
}
return qpre;
}

从尾到头打印单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int maxn = 1010;    	//数组无法变长,尽量设一个最大值可以容下链表结点数
void reversePrint(ListNode *head){ //原文用cpp且返回变长数组,此处仅仅只是打印,且没用std
if(head === NULL)
return; //日常判空
int print[maxn];
int top = -1;
while(top != -1 || head != NULL){
print[++top] = head->data;
head = head->next;
}
while(top>=0){
printf("%d",print[top--]);
if(top>0)
printf(" ");
}
}

带环的单链表中,找到环的起始点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
ListNode* meetingNode(ListNode *p){	//判断是否有环,快慢指针的方法
if(p == NULL || p->next == NULL)
return NULL;
ListNode *slow = p, *fast = p;
while(fast->next != NULL && fast->next->next !=NULL){ //一快一慢,有环必定相遇
slow = slow->next;
fast = fast->next->next;
if(fast == slow)
return fast;
}
return NULL;
}

ListNode* entryNode(ListNode *p){ //找到环的入口结点
ListNode *meeting = meetingNode(p);
if(meeting == NULL) return NULL; //无环或者空链表
int loopNodes = 1;
ListNOde *node = meeting;
while(node->next != meeting){
node = node->next;
loopNodes++; //计算环的长度
}

ListNode *head = p;
for(int i=0;i<loopNodes;i++)
head = head->next;

ListNode *another = p;
while(head != another){
head = head->next;
another = another->next;
}

return head;
}

判断两个单链表相交的第一个交点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//由于有重复操作,封装一些重复的方法还是有必要的
int getLength(ListNode *p){ //获取链表长度
int num = 0;
while(p!=NULL){
p=p->next;
num++;
}
return num;
}

ListNode* longMustWalk(ListNode *p,int k){ //长链必须先移到和短链一样长度的起点处
ListNode *q = p;
while(k>=0){
q = q->next;
}
return q;
}

ListNode* findfirstCommom(ListNode* p, ListNode* q){ //找到第一个交点
int lenp = getLength(p);
int lenq = getLength(q);
if(lenp>lenq) p = longMustWalk(p,len1-len2);
else q = longMustWalk(q,len2-len1); //让长的那一条,先走掉长-短的结点数
while(p!=NULL && q!=NULL && p!=q){
p = p->next;
q = q->next;
}

return p;
}

删除链表中重复的结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
ListNode* delduplication(ListNode* p){		//重复的全部删掉,不保留
if(p == NULL || p->next == NULL)
return p;
ListNode* q = (ListNode*)malloc(sizeof(struct Node));
q->data = -1;
q->next = p; //此处为若头结点被删除的处理
ListNode *pre = q, *r = p, *next = NULL;
//对应前驱,工作指针,next指针
while(r!=NULL && r->next != NULL){
next = r->next;
if(r->val == next->val){
while(next != NULL && r->val == next->val)
next = next->next;
pre->next = next;
r = next;
}
else{
pre = r;
r = next;
}
}
return q->next; //返回的是有带头结点的
}

阅读原文

本文标题:(单)链表常见算法(一)

文章作者:JarryChen

发布时间:2019年10月20日 - 05:20

最后更新: 2019年12月15日 22:04

原始链接: https://jarrychen.xyz/archives/c87fc611.html

× 请我喝奶茶~
打赏二维码