数据结构之链表+常见面试题

之前的一篇博客讲了一下顺序表中的顺序表，这次来谈谈线性表中的另外一种结构链表。

链表在物理上不一定连续，但是在逻辑上连续。

基本结构

单链表：

 双链表

 循环链表

总的来说应该有八种链表结构，可以分为一下几个特征进行组合

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 = 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 = 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;
}

目前暂时列举几题初阶的链表题目，后期会更新稍微有难度的常见的链表进阶面试题。