目录
顺序表缺点
链表的概念和结构
链表的分类
链表的实现
链表应用OJ题
顺序表和链表优缺点对比
顺序表缺点
顺序表随机访问很方便,但是也会有不足啊:
(1)挪动数据时间开销较大:头部/中间的插入删除,需要挪动后面的所有数据,时间复杂度为O(N)
(2)增容有代价:增容需要重新申请空间,拷贝数据,释放旧空间,系统消耗不小
(3)空间浪费:增容一般增至原来的2倍大空间,会有空间浪费,假如当前容量为100,满了以后增容到200,再继续插入了5个数据,后面没有插入数据了,这就浪费了95个空间。
不存在扩容代价、不存在空间浪费、按需申请空间、头部或者中间插入数据而不需要挪动数据的链表可以解决以上问题。
链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
注意:
(1)链式结构在逻辑上连续,逻辑上不一定连续。(逻辑结构是想象的,物理结构是内存中实际存储的)。
(2)结点一般从堆上申请。
(3)堆上申请的空间时按照一定策略分配的,两次申请的空间可能连续也可能不连续。
链表的分类
有8种链表结构 :
(1)单向和双向
(2)带头单链表和不带头单链表
(3)非循环链表和循环链表
以上3种分类的链表一共有2*2*2=8种组合,最实用的有两种:
(1)无头单向非循环链表:结构简单,一般不会用来单独存储数据。十几种更多是作为其他数据结构的子结构,如哈希桶,图的邻接表等。
(2)带头双向循环链表:结构最复杂,一般用来单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。虽然结构复杂,但是使用代码实现以后会发现该结构会带来很多优势,实现反而简单。
链表的实现
如果需要交换两个int的值,那么swap函数的实参是两个int的地址,形参是两个int型指针。
#define _CRT_SECURE_NO_WARNINGS 1 #includevoid swap(int* pa, int* pb)//用两个指针作为形参接收两个地址 { int temp = *pa; *pa = *pb; *pb = temp; } int main() { int a = 3; int b = 5; swap(&a, &b);//实参是两个int的地址 printf("a = %dn", a); printf("a = %dn", b); return 0; }
同理,对于链表的增删,如果需要改变指针指向,就要传指针的地址,即二级指针。
链表实现:
025-SList.h 链表函数定义
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; //单向+不带头+非循环 //打印 void SListPrint(SLTNode* plist); //尾插(需要改变指针指向,就要传指针的地址,即二级指针,如需要交换两个int的值,那么swap函数的实参是两个int的地址,形参是两个int型指针) void SListPushBack(SLTNode** plist,SLTDataType x); //头插 void SListPushFront(SLTNode** plist, SLTDataType x); //尾删 void SListPopBack(SLTNode** plist); //头删 void SListPopFront(SLTNode** plist); //单链表查找 SLTNode* SListFind(SLTNode* plist, SLTDataType x); //在pos之后插入x void SListInsertAfter(SLTNode* pos, SLTDataType x); //在pos之前插入x void SListInsertBefore(SLTNode** plist,SLTNode* pos, SLTDataType x); //在pos之前插入x,没有头的情况:后插一个值为x的节点,再跟前面的结点值交换。 void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x); //删除后一个节点 void SListEraseAfter(SLTNode* pos); //删除当前位置 void SListEraseCur(SLTNode** plist, SLTNode* pos);
025-SList.c 链表函数实现
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include#include #include #include "025-SList.h" //打印 void SListPrint(SLTNode* plist) { SLTNode* cur = plist; //找空节点,找到后不再打印 while (cur != NULL) { printf("%d->", cur->data); //让cur指向下一个节点 cur = cur->next; } printf("NULLn"); } //创建新节点 SLTNode* BuySLTNode(SLTDataType x) { //申请空间 SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode)); if (node == NULL) { return NULL; } //数据赋值 node->data = x; //指针赋值 node->next = NULL; return node; }
(1)尾插:
//尾插 void SListPushBack(SLTNode** pplist, SLTDataType x) { SLTNode* newNode = BuySLTNode(x); //不能使用tail->next != NULL直接作为判断条件,因为有可能是空链表,对空指针解引用会造成非法访问,因此要分两种情况 if (*pplist == NULL)//链表为空 { *pplist = newNode; } else //链表不为空 { SLTNode* tail = *pplist; //找尾节点 while (tail->next != NULL) { tail = tail->next; } tail->next = newNode; } }
(2)头插,不需要区分空链表和非空链表
//头插 void SListPushFront(SLTNode** pplist, SLTDataType x) { SLTNode* newNode = BuySLTNode(x); newNode->next = *pplist;//新节点的下一个指向第一个节点 *pplist = newNode;//链表指向新节点 }
(3)尾删
//尾删 void SListPopBack(SLTNode** pplist) { //链表为空 if (*pplist == NULL) { return; } //链表只有一个结点 else if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } //链表有多个结点 else { SLTNode* pre = NULL;//后面用该结点指向尾节点的前驱结点,因为删除为节点后,尾节点的前驱结点的后继结点要赋为空指针 SLTNode* tail = *pplist; //寻找最后一个结点,循环结束后,tail为尾结点,pre为尾结点的前驱结点 while (tail->next != NULL) { pre = tail; tail = tail->next; } free(tail); tail = NULL; pre->next = NULL; } }
(4)头删
//头删 void SListPopFront(SLTNode** pplist) { if (*pplist == NULL) { return; } else { SLTNode* next = (*pplist)->next;//保存后一个节点 free(*pplist); *pplist = next;//链表指向下一个节点 } }
(5)单链表查找
//单链表查找 SLTNode* SListFind(SLTNode* plist, SLTDataType x) { SLTNode* cur = plist; while (cur)//没找到就往后继续走 { if (cur->data == x) { return cur;//找到了就返回 } cur = cur->next; } return NULL; }
(6) 在pos之后插入
//在pos之后插入 void SListInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newNode = BuySLTNode(x);//插入需要先创建结点 newNode->next = pos->next;//新节点的下一个指向pos的下一个 pos->next = newNode;//pos的下一个指向新节点 }
(7)在pos之前插入x
//在pos之前插入x void SListInsertBefore(SLTNode** pplist, SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newNode = BuySLTNode(x); //第一个节点就是pos,即头插 if (pos == *pplist) { newNode->next = pos; *pplist = newNode; } else { SLTNode* prev = NULL;//用来记录pos的前一个结点 SLTNode* cur = *pplist; while (cur != pos)//找pos { prev = cur; cur = cur->next; } newNode->next = cur;//新节点的下一个指向pos,此时跳出while循环的cur=pos prev->next = newNode;//前一个结点的下一个指向新节点 } }
(8)在pos之前插入x,没有头(plist):后插一个值为x的节点,再跟前面的结点值交换
//在pos之前插入x,没有头(plist)的情况:后插一个值为x的节点,再跟前面的结点值交换。 void SListInsertBeforeNoHead(SLTNode* pos, SLTDataType x) { assert(pos); SLTNode* newNode = BuySLTNode(x); //后插新节点 newNode->next = pos->next; pos->next = newNode; //将新结点的值和pos的值进行交换 SLTDataType temp = pos->data; newNode->data = temp; pos->data = x; }
(9)删除后一个结点
//删除后一个节点 void SListEraseAfter(SLTNode* pos) { assert(pos); if (pos->next == NULL) { return; } SLTNode* next = pos->next; pos->next = next->next;//pos的下一个指向pos的下一个结点的下一个结点 free(next); next = NULL; }
(10) 删除当前位置
//删除当前位置 void SListEraseCur(SLTNode** pplist, SLTNode* pos) { assert(pos); SLTNode* prev = NULL; SLTNode* cur = *pplist; while (cur != pos)//寻找pos { prev = cur; cur = cur->next; } prev->next = cur->next;//前一个结点的下一个指向当前结点即pos的下一个 free(cur); cur = NULL; }
025-test.c 测试代码
#define _CRT_SECURE_NO_WARNINGS 1 #include#include #include "025-SList.h" void TestSList1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SListPushFront(&plist, 0); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); SListPopBack(&plist); SListPrint(plist); } void TestSList2() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPopFront(&plist); SListPrint(plist); } void TestSList3() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 3); if (pos) { //单链表查找兼具修改功能 pos->data = 100; printf("找到了n"); } else { printf("没找到n"); } SListPrint(plist); } void TestSList4() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPrint(plist); SLTNode* pos = SListFind(plist, 3); SListInsertAfter(pos, 300); SListPrint(plist); SListInsertBefore(&plist, pos,400); SListPrint(plist); SListEraseCur(&plist, pos); SListPrint(plist); } int main() { TestSList4(); return 0; }
执行结果:
链表应用OJ题
1.删除链表中等于给定值val的所有节点,OJ链接
分析:
(1)要删除某一结点,需要保存该结点的前一个结点(删除当前节点后,前一结点应指向当前结点的下一结点),同时需要保存当前结点的下一结点(删除当前结点后,能够继续向后访问该链表)
(2)操作:
遍历链表,如果当前结点值==val,就保存当前结点的下一个结点,前一结点指向当前结点的下一结点,释放当前结点,当前结点指向下一结点;
如果当前结点值!=val,前一结点挪到当前结点位置,当前结点挪到下一结点位置。需要考虑特殊情况,第一个结点值 == val时,此时prev=NULL需要特殊处理。
不带哨兵位头结点解法:
struct ListNode* removeElements(struct ListNode* head, int val){ struct ListNode* prev = NULL; struct ListNode* cur = head; while(cur) { if(cur->val == val)//找到了 { struct ListNode* next = cur->next;//要free(cur),就必须要先保存cur的下一个结点,否则无法继续访问下一结点 if(prev == NULL)//cur是头,要删除的结点在第一个位置 { free(cur); head = next; cur = next; } else { prev->next = next; free(cur); cur = next; } } else { prev = cur; cur = cur->next; } } return head; }
带哨兵位头结点解法:
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* guardHead = (struct ListNode*)malloc(sizeof(struct ListNode)); guardHead->next = head; struct ListNode* prev = guardHead; struct ListNode* cur = head; while (cur) { if (cur->val == val) { struct ListNode* next = cur->next; prev->next = next; free(cur); cur = next; } else { prev = cur; cur = cur->next; } } head = guardHead->next; free(guardHead); guardHead = NULL; return head; }
2.反转一个单链表 OJ链接
分析:
解法一:如果只定义两个节点,当n2指向n1时,n2的下一个结点就找不到了。因此要定义3个节点,n1和n2用于翻转,n3用于迭代:n1指向NULL,n2指向n1,n3用于记录n2的下一个结点。
struct ListNode* reverseList(struct ListNode* head) { if(head == NULL || head->next == NULL) { return head; } struct ListNode* n1 = NULL,*n2 = head,*n3 = head->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) { n3 = n3->next; } } return n1; }
解法二:头插法,依次取原链表中的节点头插到新节点
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* newHead = NULL; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; }
3.链表的中间结点 OJ链接
分析:只能遍历一遍,可以用快慢指针,慢指针每次走一步,快指针每次走两步
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
4.输出链表倒数第k个结点,OJ链接
分析:如何找倒数第k个结点,可以使用快慢指针 ,让快指针先走k步,再让慢指针开始走,此时快慢指针相差k步,然后快慢指针一起向后移动,等快指针移动到链表末尾NULL时,慢指针的位置就是倒数第k个结点位置。
struct ListNode { int val; struct ListNode *next; }; struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { if(pListHead == NULL) { return NULL; } struct ListNode* slow = pListHead; struct ListNode* fast = pListHead; while(k--) { if(fast == NULL) { return NULL; } fast = fast->next; } while(fast) { slow = slow->next; fast = fast->next; } return slow; }
5.合并两个有序链表 OJ链接
分析:尾插法,找第一个结点小的链表当作新表头,找尾比较麻烦,需要遍历,因此直接定义一个尾节点tail,每次让tail指向刚插入的节点,当有一个链表走完时就停下,再把没走完的链表全部连接到tail上。
struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode* head,*tail = NULL; if(l1 == NULL) { return l2; } if(l2 == NULL) { return l1; } if(l1->val < l2->val) { head = tail = l1; l1 = l1->next; } else { head = tail = l2; l2 = l2->next; } while(l1 && l2) { if(l1->val < l2->val) { tail->next = l1; l1 = l1->next; tail = tail->next; } else { tail->next = l2; l2 = l2->next; tail = tail->next; } } if(l1 == NULL) { tail->next = l2; } else { tail->next = l1; } return head; }
6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 OJ链接
分析:申请两个链表,一个放比x小的节点,一个放比x大的节点,最后将大链表链接在小链表末尾即可。
struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Partition { public: ListNode* partition(ListNode* pHead, int x) { // 有头指针 struct ListNode* lessHead,* lessTail,*greaterHead,*greaterTail; lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode)); greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode)); lessTail->next = NULL; greaterTail->next = NULL; struct ListNode *cur = pHead; while(cur) { if(cur->valnext = cur; lessTail = lessTail->next; } else { greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } lessTail->next = greaterHead->next; greaterTail->next = NULL; pHead = lessHead->next; free(lessHead); free(greaterHead); return pHead; } };
7.链表的回文结构 OJ链接
分析:判断链表是否是回文结构,可以结合前面的题:
(1)利用快慢指针找到链表中间结点
(2)将后半部分逆置
(3)将(2)中的链表从第一个节点开始和中间结点开始同时进行访问,如果所有val相等,则链表为回文结构。
struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; struct ListNode* middleNode(struct ListNode* head) { // write code here struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { struct ListNode* cur = head; struct ListNode* newHead = NULL; while(cur) { struct ListNode* next = cur->next; cur->next = newHead; newHead = cur; cur = next; } return newHead; } bool chkPalindrome(ListNode* A) { struct ListNode* mid = middleNode(A); struct ListNode* rHead = reverseList(mid); while(A && rHead) { if(A->val != rHead->val) { return false; } else { A = A->next; rHead = rHead -> next; } } return true; }
8.输入两个链表,找出它们的第一个公共结点 OJ链表
分析:判断链表是否相交,是判断是否有两个节点地址相同,而不是判断是否有两个结点值相同。
(1)若只是判断两个链表是否相交,直接判断最后一个链表是否相等即可
(2)要找出相交的结点:
a.计算两个链表的长度,计算两个链表的长度差距
b.让长链表先走差距步,再让两个链表同时向前走,若有相同的结点即相交。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(headA == NULL || headB == NULL) { return NULL; } struct ListNode *curA = headA, *curB = headB; int lenA = 0,lenB = 0; while(curA->next) { curA = curA->next; lenA++; } while(curB->next) { curB = curB->next; lenB++; } if(curA != curB) { return NULL; } struct ListNode *longList = headA,*shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } int gap = abs(lenA - lenB); while(gap--) { longList = longList->next; } while(longList != shortList) { longList = longList->next; shortList = shortList->next; } return longList; }
9.给定一个链表,判断链表中是否有环 OJ链接
分析:
如何判断链表是否有环:使用快慢指针,慢指针一次走1步,快指针一次走2步,如果链表带环,那么快慢同时从链表起始位置开始向后走,一定会在环内相遇,此时快慢指针都有可能在环内打圈,直到相遇;否则,如果链表不带环,那么快指针会先走到链表末尾,慢指针只能在链表末尾追上快指针。
struct ListNode { int val; struct ListNode *next; }; bool hasCycle(struct ListNode *head) { struct ListNode *slow = head; struct ListNode *fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return true; } } return false; }
如果快指针不是一次走2步,而是一次走3步,一次走4步一次走x步呢?能不能判断出链表是否带环呢?
如果快指针一次走两步,当slow从直线中间移动到直线末尾时,fast又走了slow的2倍,因此当slow进环时,fast可能在环的任意位置,具体要看直线有多长,环有多大。在环内,一定是fast追slow,因为fast比slow移动的快。
fast一次走3步:假设slow进环的时候,fast跟slow相差N步,环的长度为C,追击时,slow走1步,fast走3步,每走1次,差距就缩小2,如下图所示:
因此对于N,如果N为奇数,一定不会相遇 ,差距为:N,N-2,N-4,···,1,-1(-1即C-1,一直是fast在追slow)
如果N为奇数,一定会相遇 ,差距为:N,N-2,N-4,···,2,0
那么根据以上推论,如果fast一次走4步, 如果N为奇数,差距为:N,N-3,N-6,···,4,1,-2, 如果N为奇数,差距为:N,N-3,N-6,···,5,2,-1
总结:如果slow进环时,slow和fast的差距N是奇数,且环的长度C为偶数(则C-1为奇数,上面举例可以看出差距最小为1或-1),那么就永远追不上了。
10.给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL OJ链接
如何求环的入口点?假设起点到入口点的距离是L,假设相遇点到入口点的距离是X,假设环的大小是C,相遇时,快指针已经在环内打转了N圈,那么慢指针走的路程为L+X,快指针走的路程为L+N*C+X,则有以下公式恒成立:
根据以上公式,则有L=N*C-X。因此,如果让快指针从相遇点出发,慢指针从起点出发,它们会在入口点相遇,此时快指针已经在圈内打转了N圈,快指针走的路程为N*C-X,慢指针走的路程为L。
struct ListNode { int val; struct ListNode *next; }; struct ListNode* detectCycle(struct ListNode* head) { struct ListNode* slow = head; struct ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { struct ListNode* meet = fast; while (meet != head) { meet = meet->next; head = head->next; } return meet; } } return NULL; }
11.给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深度拷贝。OJ链接
(1)next如何处理?直接将结点拷贝下来是有问题的,把7拷贝下来指向的还是原来的13,而不是新创建的结点13,虽然值都是13,但是地址却不同。
所以要malloc之后,把值拷贝出来,然后把拷贝结点7的next指向原结点13。
(2)拷贝节点的random如何处理?如果直接处理,效率太低
a.拷贝以后,新链表需要确定每个random,需要去链表中查找,时间复杂度是O(N),每个random都要处理就是O(N*N),效率低
b.如果链表中存在节点的值相同,那么就更复杂了,比如有多个节点的值是7,那么原链表random有几个指向7的节点呢?新链表的random分别对应哪个7呢?毕竟各个7的地址不同。
把拷贝结点链接在原结点的后面,当找到原结点13的random结点7就能找到原结点7的拷贝结点,因为拷贝结点就是链接在原结点的后面,原结点13的random指向原结点7,拷贝结点13的random指向拷贝结点7。拷贝结点的random等于原结点random的next,即找到原结点就找到拷贝结点了。
(3)不能先让原结点7指向拷贝7,否则原结点7找不到原结点13了,应该让原结点7的copy结点7指向原结点7的next结点13。
struct Node* copyRandomList(struct Node* head) { if (head == NULL) { return NULL; } //1.将拷贝结点挂在原结点后面,建立对应关系 struct Node* cur = head; while (cur) { struct Node* next = cur->next; struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; cur->next = copy; copy->next = next; cur = next; } //2.处理copy结点的random cur = head; while (cur) { struct Node* copy = cur->next; if (cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = copy->next; } //3.将拷贝结点取下来链接到一起,恢复原链表 cur = head; struct Node* copyHead, * copyTail; copyHead = copyTail = (struct Node*)malloc(sizeof(struct Node)); while (cur) { struct Node* copy = cur->next; struct Node* next = copy->next; //尾插 copyTail->next = copy; copyTail = copyTail->next; cur = next; } struct Node* guard = copyHead; copyHead = copyHead->next; free(guard); return copyHead; }
12.链表的插入排序 OJ链接
struct ListNode* insertionSortList(struct ListNode* head) { //1.初始条件 struct ListNode* sortHead = head; struct ListNode* cur = head->next; sortHead->next = NULL; while(cur)//2.终止条件 { //3.迭代条件 struct ListNode* next = cur->next; //将cur结点插入到前面有序区间 struct ListNode* p = NULL, * c = sortHead; while(c) { if(cur->val < c->val) { break; } else { p = c; c = c->next; } } if(p == NULL) { cur->next = c; sortHead = cur; } else { p->next = cur; cur->next = c; } cur = next; } return sortHead; }
顺序表和链表优缺点对比
顺序表 | 链表 | |
优点 | 1.按下标随机访问 2.CPU高速缓存命中率高 | 1.按需申请内存,不存在空间浪费 2.任意位置O(1)时间内插入删除数据 |
缺点 | 1.空间不够需增容(性能消耗及空间浪费) 2.头部或中间插入删除数据,需要挪动数据,效率低,时间复杂度O(n) | 1.不支持下标随机访问 2.访问数据需要遍历,时间复杂度O(N) |
顺序表和链表是相辅相成的,互相弥补对方的缺点,需要用顺序表还是链表存储数据,具体是看场景。