【笔记】链表常见操作
# 链表常见类型***每一种新数据结构的出现都是为了解决原有数据结构的不足***。链表的出现正是为了补充数组只能连续存储的不足。这种离散存储的方式自然携带了动态存储的特性。
## 单链表
**单链表** 是链表中最为常见的链表形式，链表中只有一个指向下一结点的指针。链表中的最后一个结点通常指向 NULL，表示链表的结束。
```c
//Definition for singly-linked list.
struct ListNode {
int val;
struct ListNode *next;
};
```
单链表有一种特殊形式就是 **循环链表**，即最后一个结点指向头结点，整个链表形成一个环路
```c
struct ListNode *p1,*p2,*p3;
p1->next = p2;
p2->next = p3;
p3->next = p1;
```
## 双向链表
**双向链表** 与单链表不同的是双向链表中存放了两个指针，pre 指向上一节点， next 指向下一结点。这种链表形式完善了单链表只能向下遍历的缺陷。
```c
//Definition for double-linked list.
struct ListNode {
int val;
struct pre *next;
struct ListNode *next;
};
struct ListNode *head,*p,*end;
head->pre = NULL; head->next = p;
//头结点的上一结点指向 NULL
p->pre = head; p->next = end;
end->pre = p; end->next = NULL;
// 尾结点的下一结点指向 NULL
```
# 链表操作
## 链表的插入
链表的插入大致可分为两种情况，头结点插入和中间结点插入（尾结点插入与中间结点插入操作类似）
<center>头结点插入</center>
***思路***：让插入结点指向原头结点，指向原头结点的指针指向插入结点
```c
struct ListNode *head,*p;
//设 head 为指向头结点的指针，p 为待插入结点
p->next = head->next;
head = p;
```
<center>中间结点插入</center>
***思路***：让插入结点指向插入点的下一结点，指向插入点指向插入结点
```c
struct ListNode *p,*insertNode;
//设 p 为插入结点，insertNode 为待插入结点
insertNode->next = p->next;
p->next= insertNode;
```
## 链表的删除
链表的删除可以分为两种情况：
头结点删除：
```c
struct ListNode *head;
//设 head 为指向头结点的指针
head = head->next;
// 头结点已变成下一结点，原头结点从链表中删除
```
中间结点删除：（尾结点删除与中间结点删除操作类似）
```c
//设 p 为待删除结点，preNode 为待删除结点的上一节点
struct ListNode *p,*pretNode;
// 可以直接 pretNode->next = pretNode->next->next;
pretNode->next = p->next;
```
## 有序链表的合并
***思路：*** 合并两个有序链表只需要每次找出当前结点最小值，放入归并链表中。让更小结点链表向下遍历，直至两条链表都遍历完成即完成了两个有序链表的合并
```c
List *mergeTwoLists(List *list1, List *list2)
{
if (!list1&&!list2) return NULL;
//当两条链表都为遍历结束则返回 NULL
else if (!list1) return list2;
//因为都是有序则一条遍历结束后只要将另一条链表接在后面即可
else if (!list2) return list1;
else if (list1->val<list2->val)
{
list1->next = mergeTwoLists(list1->next, list2);
return list1;
}
else
{
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
```
## 单链表翻转
***思路：*** 需要有三个指针，分别指向：上一节点、当前结点、下一结点。
```c
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode* new_head=NULL,*node=NULL;
while (head!=NULL)
{
new_head = head;//新的头结点等于当前结点
head = head->next;//当前结点变成下一结点
new_head->next = node;//当前结点的下一结点为上一结点，从空指针开始
node = new_head;//上一节点变成当前结点，以此循环，达到链表反转的效果
}
return node;
}
```
## 单链表的环路检测
***思路：*** 通常用快慢指针来处理类似题目，快指针以慢指针两倍速遍历单链表，若快指针遍历到 NULL 则无环路，若快指针与慢指针指向同一结点，则单链表有环路。
```c
bool hasCycle(struct ListNode *head) {
struct ListNode *slow,*fast;
slow=fast=head;
while(fast&&fast->next&&fast->next->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
return true;
}
return false;
}
```
## 有序单链表的重复检测
***思路：*** 因为链表是有序的，若下一结点的值与当前结点的值相等则删除该结点
```c
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode* p = head;
while (p&&p->next)
{
if (p->val == p->next->val)
p->next=p->next->next;
else
p=p->next;
}
return head;
}
``` 有什么入门的数据结构 书吗 天才第一步 发表于 2019-3-2 21:26
有什么入门的数据结构 书吗
《算法》和《算法导论》是最经典的，《算法图解》是很适合入门看的。其他的可以根据语言选择，例如我 C 语言看的是 《数据结构与算法分析 C语言描述》
页:
[1]