线性表之链表

无头单向链表
.h

#pragma once#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<windows.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<errno.h>
#include<stddef.h>typedef int SLTDataType;struct SListNode
{SLTDataType data;struct SListNode* next;
};typedef struct SListNode SLTNode;//不可能改变链表的头指针，传一级指针
void SListPrint(SLTNode* phead);//可能改变链表的头指针，传二级指针
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SListPushFront(SLTNode** pphead, SLTDataType x);void SListPopFront(SLTNode** pphead);
void SListPopBack(SLTNode** pphead);SLTNode* SListFind(SLTNode* phead, SLTDataType x);//pos的前面插入x
void SListInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x);
//删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos);

#include "SList.h"void SListPrint(SLTNode* phead) {SLTNode* cur = phead;while (cur != NULL){printf("%d ", cur->data);cur = cur->next;}
}SLTNode* BuySListNode(SLTDataType x) {SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));newnode->data = x;newnode->next = NULL;return newnode;
}
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找到尾节点的指针SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}//尾节点链接新节点tail->next = newnode;}
}void SListPushFront(SLTNode** pphead, SLTDataType x) {SLTNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SListPopFront(SLTNode** pphead)
{SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}void SListPopBack(SLTNode** pphead) {if (*pphead == NULL){return;}else if ((*pphead)->next == NULL) {  //只有一个节点free(*pphead);*pphead = NULL;}else {SLTNode* tail = *pphead;SLTNode* prev = NULL;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);prev->next = NULL;}
}SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x) {return cur;}cur = cur->next;}return NULL;}void SListInsert(SLTNode** pphead, SLTDataType* pos, SLTDataType x) {SLTNode* newnode = BuySListNode(x);SLTNode* prev = *pphead;if (prev == pos){SListPushFront(pphead,x);}else {while (prev->next != pos) {prev = prev->next;}prev->next = newnode;newnode->next = pos;}}void SListErase(SLTNode** pphead, SLTNode* pos)
{SLTNode* prev = *pphead;if (prev == pos){SListPopFront(pphead);}else {while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);}}

test。c

#include "SList.h"void TestSList1()
{SLTNode* plist = NULL;SListPushBack(&plist, 1);SListPushBack(&plist, 2);SListPushFront(&plist, 0);SLTNode* pos = SListFind(plist, 2);SListInsert(&plist, pos, 999);pos = SListFind(plist, 0);SListInsert(&plist, pos, 999);pos = SListFind(plist, 999);SListErase(&plist, pos);SListPrint(plist);
}int main()
{TestSList1();return 0;
}

有哨兵位双向循环链表
最优的链表，在任意位置操作都是O(1)
查找有平衡搜索树（AVL树和红黑树），哈希表，B树，B+树

#pragma once#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<windows.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<errno.h>
#include<stddef.h>typedef int LTDataType;//SList  single
//DList  double 在c++里直接叫Listtypedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}ListNode;ListNode* ListInit();void ListDestroy(ListNode* phead);
void ListPrint(ListNode* phead);void ListPushBack(ListNode* phead,LTDataType x);
void ListPushFront(ListNode* phead, LTDataType x);void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);ListNode* ListFind(ListNode* phead, LTDataType x);//其实insert跟erase可以去套用在头尾插删
void ListInsert(ListNode* pos, LTDataType x); //pos位置之前插入
void ListErase(ListNode* pos);

#include "List.h"ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}ListNode* ListInit()
{ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;
}void ListDestroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}void ListPrint(ListNode* phead) {ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}void ListPushBack(ListNode* phead, LTDataType x)  //STL中源码就是这个结构
{assert(phead);ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);//先把tail和newnode建立联系tail->next = newnode;newnode->prev = tail;//再把phead跟newnode建立联系newnode->next = phead;phead->prev = newnode;}void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}void ListPopFront(ListNode* phead)
{assert(phead);assert(phead->next != phead); //只剩phead的时候不删ListNode* first = phead->next;ListNode* second = first->next;phead->next = second;second->prev = first;free(first);first = NULL;
}void ListPopBack(ListNode* phead)
{assert(phead);assert(phead->next != phead); //只剩phead的时候不删ListNode* tail = phead->prev;ListNode* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;}ListNode* ListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}void ListInsert(ListNode* pos, LTDataType x) //pos位置之前插入
{assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}

#include "List.h"void TestList1()
{ListNode* plist = ListInit();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 333);ListPushFront(plist, 0);ListNode*pos = ListFind(plist, 2);if (pos){printf("找到了,并且把值乘十\n");pos->data *= 10; //查找同时可以充当修改}else {printf("没找到\n");}ListInsert(pos, 999);ListPrint(plist);ListDestroy(plist);
}
int main()
{TestList1();return 0;
}

力扣206 反转链表

思路一：翻指针的方向
重复的过程使用循环
1.初始条件
2.迭代过程
3.结束条件

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*///思路一：翻指针的方向
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL){return NULL;}struct ListNode*n1=NULL,*n2=head,*n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n2->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;
}

876.给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

只遍历链表一边的方法：快慢指针
slow走一步，fast走两步

struct ListNode* middleNode(struct ListNode* head) {struct ListNode*slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;}return slow;

141.环形链表

使用快慢指针

bool hasCycle(struct ListNode* head) {struct ListNode *fast = head, *slow = head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){return true;}}return false;
}