目录
一、概念与结构
二、实现单链表
三、链表的分类
四、单链表算法题
一、概念与结构
1、节点
结点的组成主要有：当前结点要保存的数据和保存下一个节点的地址（指针变量）
图中指针变量plist保存的是第一个结点的地址，我们称plist此时“指向”第一个结点。
链表中每个结点都是独立申请的（如果需要插入数据时才去申请一块结点的空间），我们需 要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。
2、链表的性质
【链表机构在逻辑上是连续的，在物理结构上不一定连续。
【结点一般是从堆上申请的。
【从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。
二、实现单链表
1、创立文件
2、定义链表的结构
【SList.h】
//定义链表(结点)的位置
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);3、打印函数
【SList.h】
//打印函数
void SLTPrint(SLTNode* phead);【SList.c】
//打印函数
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}【test.c】
//创建一个链表，并且打印链表
void createSList()
{SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//第一个结点的地址作为参数传递过去SLTNode* plist = node1;SLTPrint(node1);
}4、判断插入时，空间是否足够
【SList.c】
//判断插入数据时，空间是否足够
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = NULL;return node;
}5、尾插
【SList.h】
//尾插
void SLTPushBack(SLTNode** pphead,SLTDataType x);【SList.c】
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//形参：pphead --> 实参：&plist//*pphead 解引用 --> plist//申请新结点SLTNode* newnode = SLTBuyNode(x); //判断是否有足够空间if (*pphead == NULL){*pphead = newnode;}else{//尾节点 --> 新结点//找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail --> newnodeptail->next = newnode;}
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPrint(plist); //1->NULLSLTPushBack(&plist, 2);SLTPrint(plist); //1->2->NULLSLTPushBack(&plist, 3);SLTPrint(plist); //1->2->3->NULLSLTPushBack(&plist, 4);SLTPrint(plist); //1->2->3->4->NULL
}【运行结果】
6、头插
【SList.h】
//头插
void SLTPushFront(SLTNode** pphead,SLTDataType x);【SList.c】
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x); //判断是否有足够空间//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULL
}
【运行结果】
7、尾删
【SList.h】
//尾删
void SLTPopBack(SLTNode** pphead);【SList.c】
//尾删
void SLTPopBack(SLTNode** pphead)
{//判断链表是不是空，若为空则不可以删assert(pphead && *pphead);//处理只有一个结点的情况：要删除的就是头结点（当next指针为空）if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾结点ptail 和尾结点的前一个结点prevSLTNode* ptail = *pphead;SLTNode* prev = NULL;//遍历数组,找尾结点while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);//尾删SLTPopBack(&plist);SLTPrint(plist); //4->3->2->NULLSLTPopBack(&plist);SLTPrint(plist); //4->3->NULLSLTPopBack(&plist);SLTPrint(plist); //4->NULLSLTPopBack(&plist);SLTPrint(plist); //NULL
}【运行结果】
8、头删
【SList.h】
//头删
void SLTPopFront(SLTNode** pphead);【SList.c】
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//删除*pphead --> nextfree(*pphead);*pphead = next;
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);//SLTPrint(plist); //4->3->2->1->NULL//头删SLTPopFront(&plist);SLTPrint(plist); //3->2->1->NULLSLTPopFront(&plist);SLTPrint(plist); //2->1->NULLSLTPopFront(&plist);SLTPrint(plist); //1->NULLSLTPopFront(&plist);SLTPrint(plist); //NULL
}
【运行结果】
9、查找
【SList.h】
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);【SList.c】
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//跳出循环，说明没找到return NULL;
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);//SLTPrint(plist); //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 3);if (find == NULL){printf("没找到！\n");}else{printf("find it!\n");}
}
【运行结果】
10、在指定位置之前插入数据
【SList.h】
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);【SList.c】
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//如果pos恰好是头结点if (pos == *pphead){SLTPushFront(pphead, x); //相当于头插}else{SLTNode* newnode = SLTBuyNode(x);//找到pos的前一个结点:prevSLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//跳出这个循环，说明prev的前一个结点就是pos//将newnode插入prev和pos之间newnode->next = pos;prev->next = newnode;}
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//在指定位置之前插入数据SLTInsert(&plist, find, 11); //在2之前插入11SLTPrint(plist); //4->3->11->2->1->NULL
}【运行结果】
11、在指定位置之后插入数据
【SList.h】
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);【SList.c】
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//把newnode放到pos的下一个位置（pos->next）newnode->next = pos->next;pos->next = newnode;
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//在指定位置之后插入数据SLTInsertAfter(find, 9); //在2之后插入9SLTPrint(plist); //4->3->2->9->1->NULL
}
【运行结果】
12、删除pos结点
【SList.h】
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);【SList.c】
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pos);assert(pphead && *pphead);//头插（如果pos恰好为头结点*pphead,那就没有前一个结点prev了）if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){ //遍历数组，寻找posprev = prev->next;}//跳出循环，prev刚好是pos的前一个结点(要删除pos)prev->next = pos->next;free(pos);pos = NULL;}}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//删除pos结点SLTErase(&plist, find); //删除pos(2)这个结点SLTPrint(plist); //4->3->1->NULL
}【运行结果】
13、删除pos之后的结点
【SList.h】
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);【SList.c】
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->next);//删除pos的下一个结点，就要让pos的下一个结点直接指向pos的next的next//但是后面要把pos->next释放删除掉，所以先把这个指针保存起来SLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//删除pos之后的结点SLTEraseAfter(find);SLTPrint(plist); //4->3->2->NULL
} 【运行结果】
14、销毁链表
【SList.h】
//销毁链表
void SListDestroy(SLTNode** pphead);【SList.c】
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}【test.c】
void SListTest01()
{SLTNode* plist = NULL;//头插SLTPushFront(&plist, 1);SLTPushFront(&plist, 2);SLTPushFront(&plist, 3);SLTPushFront(&plist, 4);SLTPrint(plist); //4->3->2->1->NULL//查找SLTNode* find = SLTFind(plist, 2);//销毁链表SListDestroy(&plist);SLTPrint(plist); //NULL
} 【运行结果】
三、链表的分类
四、单链表算法题
1、反转链表
【思路】
【代码】
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{//处理空链表if(head == NULL){return head;}//创建三个指针ListNode* n1,*n2,*n3;n1 = NULL , n2 = head , n3 = n2->next; while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}//此时n1就是链表反转后新的头结点headreturn n1;
}2、链表的中间结点
【思路】
【代码】
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head,*fast = head;//慢指针每次走一步//快指针每次走两步while(fast && fast->next) //等价于fast!=NULL && fast->next!=NULL
//当fast或fast->fast任何一个为空指针（为假）时，就跳出循环{slow = slow->next;fast = fast->next->next;}//此时slow指向得节点刚好就是中间节点return slow;}3、合并两个有序链表
【思路】
【代码】
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{//处理链表为空的情况if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//创建新链表ListNode*newHead = NULL,*newTail = NULL;//创建两个指针分别指向两个链表的头结点ListNode* l1 = list1;ListNode* l2 = list2;//比大小while(l1 && l2){if(l1->val < l2->val){//l1尾插到新链表中if(newHead == NULL){newHead = newTail = l1;}else{newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{//l2尾插到新链表if(newHead == NULL){newHead = newTail = l2;}else{newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}//跳出while循环，只有两种情况：l1为空（l2肯定不为空） 或 l2为空（l1不为）if(l1) //l1不为空{newTail->next = l1;}if(l2) //l2不为空{newTail->next = l2;}return newHead;
}4、链表分割
【思路】
【代码】
class Partition
{
public:ListNode* partition(ListNode* pHead, int x) { //创建两个非空链表：小链表、大链表//小链表ListNode* lessHead,*lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));//大链表 ListNode* greaterHead,*greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历原链表，与x比较大小// >=x的尾插进入大链表 ， <x的尾插进入小链表ListNode* pcur = pHead;while(pcur) //等价于pcur != NULL{if(pcur->val < x){ //尾插到小链表lessTail->next = pcur;lessTail = lessTail->next;}else { //尾插到大链表greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//将大链表的尾结点的next置为空greaterTail->next = NULL;//让大小链表首尾相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;}
};5、链表的回文结构
【代码】
class PalindromeList
{
public:
ListNode* findMidNode(ListNode* phead)
{//使用快慢指针，寻找中间结点ListNode* slow = phead;ListNode* fast = phead;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}ListNode* reverseList(ListNode* phead)
{//链表反转ListNode* n1,*n2,*n3;n1 = NULL;n2 = phead;n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;
}bool chkPalindrome(ListNode* A) {//1、找中间结点ListNode* mid = findMidNode(A);//2、根据中间结点，将中间结点后的链表反转ListNode* right = reverseList(mid);//3、从原链表的头和反转链表比较结点值 (开始时，left指头，right指尾)ListNode* left = A;while(right){if(left->val != right->val){return false;}left = left->next;right = right->next;}return true;}
};未完待续...
