数据结构|数据结构之链表+常见面试题单链表|数据结构|c语言|指针

之前的一篇博客讲了一下顺序表中的顺序表，这次来谈谈线性表中的另外一种结构链表。
链表在物理上不一定连续，但是在逻辑上连续。
基本结构单链表：

文章图片

双链表

文章图片

循环链表

文章图片

总的来说应该有八种链表结构，可以分为一下几个特征进行组合
1、单向、双向
2、带头、不带头
3、循环、非循环
例如单向不带头非循环链表就是画的第一种结构，以此类推。
单链表的实现节点的基本结构

typedf struct Link_list { int data; //存放的数据 struct Link_list* next; //指向下一个数据的指针 }Link_list;

尾插

//开辟一个新的节点 Link_list* AddNote(const int elements) { Link_list* newnote = (Link_list*)malloc(sizeof(Link_list)); newnote->data = https://www.it610.com/article/elements; newnote->next = NULL; return newnote; } //如果不是空链表，这种情况就只需要传一级指针 void AddElements(Link_list *pa, const int elements) { while (pa->next != NULL) pa = pa->next; pa->next = AddNote(elements); } //------------------------------------------- //------------------------------------------- //这种情况是当链表为空的时候必须得传二级指针，因为要修改地址（第一个元素的开辟） void AddElements(Link_list **pa,const int elements) { Link_list *p=*pa; if (*pa == NULL) { *pa=AddNote(elements); return; } while ((*pa)->next != NULL) (*pa) = (*pa)->next; (*pa)->next = AddNote(elements); *pa = p; //重新指向头结点 }

头插

void AddElementsHead(Link_list **pa,int elements) { Link_list* p = AddNote(elements); p->next = *pa; *pa = p; }

头删、尾删、查找这些并不复杂，不在赘述。
带头双向循环链表虽然结构更复杂，但是对链表的操作更容易，实际上使用的也很多。
节点的基本结构

typedef struct ListNode { struct ListNode* next; struct ListNode* pre; LTDataType data; }ListNode;

双向链表的节点需要两个指针，一个指向前一个节点，一个指向后一个节点。
新建一个节点

typedef int LTDataType; ListNode* BuyListNode(const LTDataType x) { ListNode* p = (ListNode*)malloc(sizeof(ListNode)); p->data = https://www.it610.com/article/x; p->next = NULL; p->pre = NULL; return p; }

初始化头结点

//用来初始化头结点 ListNode* ListInit() { ListNode* p = BuyListNode(0); //首先都指向自己 p->next = p; p->pre = p; return p; }

尾插

void ListPushBack(ListNode* phead, const LTDataType x) { assert(phead); ListNode* p = BuyListNode(x); phead->pre->next = p; p->pre = phead->pre; phead->pre = p; p->next = phead; }

在这里面phead作为头结点，phead->pre就是该链表的尾结点，新创建的节点就应该插入到他的构面。整个插入的逻辑就是，将尾结点的next指向新开的节点p，p的pre指向尾结点，头结点的pre指向p，p的next指向头节点。
头插

void ListPushFront(ListNode* phead, const LTDataType x) { assert(phead); ListNode* p = BuyListNode(x); p->next = phead->next; phead->next->pre = p; p->pre = phead; phead->next = p; }

链表的优点缺点优点：
1、按需分配内存，不存在空间浪费，内存利用率比较高
2、插删不用挪动数据，插删快
缺点：
1、内存不连续，无法随即访问

常见的面试题（初阶） 1、删除链表中等于给定值 val 的所有节点。

struct ListNode* removeElements(struct ListNode* head, int val){typedef struct ListNode ListNode; ListNode* pre = (ListNode*)malloc(sizeof(ListNode)); //创建一个头节点 pre->next = head; //然后采用双指针的方式进行遍历 ListNode* p = head; ListNode* ptmp = pre; while(p) { if(p->val == val) { ptmp->next = p->next; p = p->next; } else { ptmp = p; p = p->next; } } return pre->next; }

2、反转一个单链表。

struct ListNode* reverseList(struct ListNode* head){typedef struct ListNode ListNode; if(head == NULL) return NULL; ListNode* p1 = head; ListNode* p2 = head->next; while(p2) { ListNode* p3 = p2->next; p2->next = p1; p1 = p2; p2 = p3; if(p3) { p3 = p3->next; } } head->next = NULL; return p1; }

3、链表的中间结点

//经典快慢指针的方法 struct ListNode* middleNode(struct ListNode* head){typedef struct ListNode ListNode; ListNode* pslow = head; ListNode* pfast = head; while(pfast&&pfast->next) { pslow = pslow->next; pfast = pfast->next->next; } return pslow; }

4、链表中倒数第k个结点

//一种简单的方法，倒数第几个节点就是正数第几个 //这种方法需要遍历两次，但是理解起来简单 //可自行实现 //--------------------------------------------//下面这种方法 //严格的O(n)复杂度 //双指针的方法，让后一个指针与前一个指针相差k个节点 //当后一个指针到链表结尾时，前一个指针刚好是倒数第k个节点的位置 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) { struct ListNode* pnext = pListHead; if(pListHead == NULL) return NULL; while(k) { if(pnext==NULL) return NULL; pnext = pnext->next; k--; } while(pnext) { pnext = pnext->next; pListHead = pListHead->next; } return pListHead; }

【数据结构|数据结构之链表+常见面试题】目前暂时列举几题初阶的链表题目，后期会更新稍微有难度的常见的链表进阶面试题。