linked list

数据结构汇总之 linked list

原文见 仓库

good good study, day day leetcode


以下是关于链表的总结。

原文可参考我github仓库上的文章 summary-LinkedList
summery-LinkedList-2

一、基本操作

链表相对于顺序表,不需要移动数据元素,只需要修改“链”,所以在某些场合要显得更灵活

0、结构初始化

图解如下:

1
2
3
4
struct ListNode {
ElementType val;
struct ListNode* next;
};


1、建立(空链表)
1
2
3
4
5
struct ListNode* CreateEmpty() {
struct ListNode* p;
p=(struct ListNode*)malloc(sizeof(ListNode));
p->next=NUll;
}


2、求表长
1
2
3
4
5
6
7
8
9
int Length(struct ListNode* p) {
int j=0;

while (p) {
p=p->next;
j++;
}
return j;
}


3、查找
1
2
3
4
5
6
//按照值查找
struct ListNode* Find(ElementType x,struct ListNode* p) {
while (p&&p->val!=x)
p=p->next;
return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
//按照序号查找
//查找第k个元素,k从1开始
struct ListNode* FindKth(int k,struct ListNode* p) {
int i=1;
while (p!=NULL&&i<k) {
p=p->next;
i++;
}

if (i==k) return p;
else return NULL;
}


4、插入(在第i-1节点后面插入)

图解如下:

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
//插入位置分两种情况:在表头/不在表头
/*
1)先构造一个新节点s
2)找到链表第i-1个节点q
3)x->next=p->next;p->next=s;(不可颠倒)
*/

struct ListNode* Insert(struct ListNode* p,int i,ElementType x) {
struct ListNode* q,s;

if (i==1) {
s=(struct ListNode*)malloc(sizeof(struct ListNode));
s->val=x;
s->next=p;
return s;
}

q=FindKth(i-1,p);
if (q==NULL)
return NULL;
else {
s=(struct ListNode*)malloc(sizeof(struct ListNode));
s->val=x;
s->next=q->next;
q->next=s;
return p;
}
}


5、删除(删除链表第i个节点)

图解如下:

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
//同理删除位置分两种:在表头/非表头
/*
1)首先找到第i-1个节点q
2)指针s指向待删除节点 s=q->next;
3)修改指针删除s节点 q->next=s->next;
4)释放s节点 free(s);
*/

struct ListNode* Delete(struct ListNode* p,int i) {
struct ListNode* q,s;

if (p==NULL) return NULL;
if (i==1) {
s=p;
p=p->next;
free(s);

return p;
}

q=FindKth(i-1,p);
if (q==NULL) return NULL;
else if (q->next==NULL) return NULL;
else {
s=q->next;
q->next=s->next;
free(s);

return p;
}
}




二、题型归纳

1、链表反转/翻转
2、链表划分/重排
3、链表合并
4、链表相交

5、环形链表

6、奇偶链表
7、回文链表
8、链表去重
9、链表深度拷贝
10、链表相加

三、技巧总结

1、虚拟表头

2、快慢指针

3、巧用数学规律

4、基础操作


-------------本文结束感谢您的阅读-------------