双向带头循环链表及链表面试题二

循环链表的实现及链表面试题二

链表

循环链表的实现

双向带头循环链表的优越性

双向循环链表:有两个指针,一个指向前一个节点,一个指向后一个节点。

值得注意的是双向带头循环链表为空时,两个指针指向head本身。
《双向带头循环链表及链表面试题二》

优点:在于可以对任意给定的节点取其前面节点和后面节点的位
置,由于可以轻易得到前后节点的位置,所以在节点的插入和删除中它的操作就相对简单。其中(头插是插在头节点head的后面,尾插是插在头节点head的前面)

缺点:是每个节点都需要保存prev和next,因此需要开辟更多的空间。
其本质:是用空间换取时间

程序部分

.h文件

# pragma once
// 带头 + 双向 + 循环链表增删查改实现
typedef int DataType;
typedef struct ListNode Node;
typedef struct ListNode
{ 
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
};

// 创建返回链表的头结点.
Node* DListCreate();
// 双向链表销毁
void DListDestory(Node* pHead);
// 双向链表打印
void DListPrint(Node* pHead);
// 双向链表尾插
void DListPushBack(Node* pHead, DataType x);
// 双向链表尾删
void DListPopBack(Node* pHead);
// 双向链表头插
void DListPushFront(Node* pHead, DataType x);
// 双向链表头删
void DListPopFront(Node* pHead);
// 双向链表查找
Node* DListFind(Node* pHead, DataType x);
// 双向链表在pos的前面进行插入
void DListInsert(Node* pos, DataType x);
// 双向链表删除pos位置的节点
void DListErase(Node* pos);

.c文件

#include "SXDList.h"
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

// 创建返回链表的头结点.

Node*  DListCreate(DataType data)
{ 
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (NULL == newNode)
	{ 
		assert(0);
		return NULL;
	}

	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;

	return newNode;
}
//双向带头循环的初始化
void DListInit(Node** head)
{ 
	assert(head);
	*head = DListCreate(0);
	//next prev 都指向head
	(*head)->next = *head;
	(*head)->prev = *head;
}

// 双向链表头插
void DListPushFront(Node* head, DataType data)
{ 	//插在头节点head下一个节点的前面
	DListInsert(head->next, data);
}
// 双向链表头删
void DListPopFront(Node* head)
{ 
	assert(head);
	DListErase(head->next);
}
//尾插
void DListPushBack(Node* head, DataType data)
{ 	//直接插在head的前面
	DListInsert(head, data);
}
//尾删
void DListPopBack(Node* head)
{ 
	assert(head);
	DListErase(head->prev);
}

// 双向链表在pos的前面进行插入
void DListInsert(Node* pos, DataType data)
{ 
	Node* newNode = NULL;
	if (NULL == pos)
		return;

	newNode = DListCreate(data);
	newNode->prev = pos->prev;
	newNode->next = pos;
	newNode->prev->next = newNode;
	pos->prev = newNode;
}
// 双向链表删除pos位置的节点
void DListErase(Node* pos)
{ 
	if (NULL == pos)
		return;

	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;

	free(pos);
}
//销毁链表
void DListDestroy(Node** head)
{ 
	assert(head);
	Node* cur = (*head)->next;
	while (cur != (*head))//如若cur走到head的位置,则被删除完了
	{ 
		(*head)->next = cur->next;//把第一个节点断开
		free(cur);
		cur = (*head)->next;
	}

	free(*head);
	*head = NULL;
}
//链表的查找
Node* DListFind(Node* head, DataType data)
{ 
	Node* cur = head;
	while (cur)
	{ 
		if (data == cur->data)
			return cur;

		cur = cur->next;
	}

	return NULL;
}

//打印
void DListPrint(Node* head)
{ 
	assert(head);
	Node* cur = head->next;
	while (cur != head)
	{ 
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}


int main()
{ 
	Node* head = NULL;
	DListInit(&head);

	DListPushBack(head, 1);//尾插
	DListPushBack(head, 2);
	DListPushBack(head, 3);
	DListPushBack(head, 4);
	DListPushBack(head, 5);
	DListPushBack(head, 6);
	DListPrint(head);

	DListPushFront(head, 0);//头插
	DListPrint(head);

	DListPopFront(head);//头删
	DListPrint(head);
	//找到4的位置删除
	DListErase(DListFind(head, 4));
	DListPrint(head);

	DListPopBack(head);//尾删
	DListPopBack(head);
	DListPopBack(head);

	DListPrint(head);

	DListDestroy(&head);
}

1.链表的合并

题目描述

《双向带头循环链表及链表面试题二》

解题思路

1.判断两个链表,是否为空,当其中一个链表为空时,返回另一个。
2.如果都不为空,只需将链表中的节点逐个往新链表中进行尾插,将较小的值插入到新链表。
3.当出现其中一个链表为空,就是插完的情况,需要把令一个链表的剩余值插入到新链表中

程序部分

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){ 
    if(NULL==l1)
        return l2;
    
    if(NULL==l2)
        return l1;

        //两个链表均不为空
        //只需将链表中的节点逐个往新链表中进行尾插
        //每次插入较小的节点
        ListNode newHead;//运行结束后,空间会被回收
        ListNode* cur1=l1,*cur2=l2;
        ListNode* tailNode=&newHead;
        while(cur1&&cur2)//cur1和cur2中还有节点
        { 
            if(cur1->val<cur2->val)
            { 
                tailNode->next=cur1;
                cur1=cur1->next;
            }
            else
            { 
                tailNode->next=cur2;
                cur2=cur2->next;
            }
            tailNode=tailNode->next;
        }

        //while循环结束后,要么cur1为空,要么cur2为空
        //已经将一个链表中的所有节点插完了
        if(cur1)
        { 
            tailNode->next=cur1;
        }
        else
        { 
            tailNode->next=cur2;
        }
        return newHead.next;

}

2.链表的分割

题目描述

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

解题思路

1.创立两个带头节点的空链表lessHead,greaterHead,
定义两个指针lessTail,greaterTail分别指向lessHead,greaterHead,指针cur指向原链表
2.当链表为空时,返回空
3.当链表不为空时,进行分割
对原链表进行遍历,当原链表中的值大于x时放入greaterHead中,小于x的值时放入到lessHead中,放入的方式为尾插,分割完成
4.进行合并,将较小链表的最后一个节点指向较大链表头节点的下一个 。

程序部分

class Partition { 
public:
    ListNode* partition(ListNode* pHead, int x)
    { 
        if(NULL==pHead)
        { 
            return NULL;
        }
        //利用带头节点的方式来实现
        //创建两个带头结点的空链表
        ListNode lessHead(0),greaterHead(0);//空间在栈上
        //结构体类型的变量 类比于int a;int b,用完就被回收,不用free
        ListNode* lessTail=&lessHead;
        ListNode* greaterTail=&greaterHead;
        ListNode*cur=pHead;
        while(cur)
        { 
            pHead=cur->next;//将第一个节点拆下来
            if(cur->val<x)
            { 
                lessTail->next=cur;
                lessTail=cur;
            }
            else
            { 
                greaterTail->next=cur;
                greaterTail=cur;
            }
            cur=pHead;
           }
        greaterTail->next=NULL;//尾部要置空防止死循环
        //合并 将较小链表的最后一个节点指向较大链表头节点的下一个
        lessTail->next=greaterHead.next;
        return lessHead.next;
        
    }
};

3判断链表是否有环

题目描述

《双向带头循环链表及链表面试题二》

解题思路

1,给两个指针 fast slow
fast每次走两步,slow每次走一步
2.按照这种方式遍历链表,如果两个指针相遇,则带环,否则fast走到链表的末端一定不带环

程序部分

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

4.链表入环的第一个节点

题目描述

《双向带头循环链表及链表面试题二》

解题思路

1.先判断链表是否带环(是否带环的方法上题已经给出)
2.如果带环,给两个指针pH,pM分别指向链表的开头,和带环的相遇点,两个指针往下走,再次相遇时则为带环链表的第一个入口点。

程序部分

struct ListNode* hasCycle(struct ListNode* head)
 { 
     struct ListNode*fast=head;
    struct ListNode*slow=head;

    while(fast&&fast->next)
    { 
        fast=fast->next->next;
        slow=slow->next;
        if(slow==fast)
        { 
            return fast;
        }
    }
    return NULL;
 }
struct ListNode *detectCycle(struct ListNode *head) 
{    
    //pM指向快慢两个指针的相遇处
   struct ListNode* pM=hasCycle(head);
    if(NULL==pM)
    { 
        return NULL;
    }
    //链表带环
    struct ListNode*pH=head;//pH指向头
    while(pH!=pM)
    { 
        pM=pM->next;
        pH=pH->next;
    }
    //相遇时为带环的入口
    return pH;

}

5.复杂链表的拷贝

题目描述

《双向带头循环链表及链表面试题二》

解题思路

1.在原链表的每个结点后面都插入一个值相等的结点
用指针cur遍历链表,申请一个新的节点,进行插入。
2.给新插入的结点的随机指针域赋值(新节点的随机指针域指向刚好是前一个结点随机指针域的下一个)
3.将新插入的节点从原链表中拆下来。(通过改变指针的指向)

程序部分

struct Node* copyRandomList(struct Node* head) 
{ 
    if(head==NULL)
    return NULL;
	struct Node*cur=head;  
    struct Node* newNode=NULL;
    //1.在原链表的每个结点后面都插入一个值相等的结点
    while(cur)
    { 
        //申请一个新节点,这个结点必须是malloc出来的
        newNode=(struct Node*)malloc(sizeof(struct Node));
        //对这个结点进行判空
        if(NULL==newNode)
            return NULL;
        newNode->next=newNode->random=NULL;
        newNode->val=cur->val;
        //将新结点插入链表
        newNode->next=cur->next;
        cur->next=newNode;
        cur=newNode->next;
    }
    //2.给新插入的结点的随机指针域赋值
    //注意:新节点的随机指针域指向刚好是前一个结点随机指针域的下一个
    cur=head;//继续从头开始遍历
    while (cur)
    { 
        newNode=cur->next;
        if(cur->random)
        { 
            newNode->random=cur->random->next;
        }
        cur=newNode->next;
    }
    //3.将新插入的节点从原链表中拆下来
    cur=head;
    struct Node* newHead=cur->next;
    newNode=newHead;//把newNode指针放在cur的next位置
    while(newNode)
    {       
        cur->next=newNode->next;
        cur=newNode;
        newNode=cur->next;
    }
    //cur->next=NULL;
    return newHead;

	
}

6.链表的插入排序

题目描述

《双向带头循环链表及链表面试题二》

解题思路

1.如果链表为空,或者只有一个节点,就没有必要进行插入排序
2.如果不为空,将原链表中的节点逐个拆下来,插入新链表。
这里分为两种情况:
如果新链表中没有元素,则直接插到新链表中;
如果新链表中有元素则需要通过比较,找到该节点的位置进行插入。
(注意在插入时需要两个指针prev pos,prev来保存pos前一个的位置,用于插入新节点)f’f’f’f’f’f’f’f’f’f’f。

程序部分

struct ListNode* insertionSortList(struct ListNode* head)
{ 
    if(NULL==head||NULL==head->next)
        return head;
    struct ListNode*cur=head;
    struct ListNode*newHead=NULL;
    struct ListNode*pos=NULL;
    struct ListNode*prev=NULL;
    while(cur)
    { 
        head=cur->next;//拆下原链表的节点
        //插入
        //找位置,插入cur
        pos=newHead;
        prev=NULL;
        while(pos)
        { 
            // 将cur中的值于pos中的值比较大于的往后走直到遇到小于pos的
            //值时跳出循环
            if(cur->val<=pos->val)
               break;
            prev=pos;
            pos=pos->next;
        }
        //直接小于pos中的第一个 插入
        if(pos==newHead)
        { 
            cur->next=newHead;
            newHead=cur;
        }
        //pos往后走,cur->插入到中间或最后一个
        else
        { 
            cur->next=pos;
            prev->next=cur;
        }
            cur=head;
    }
    return newHead;
}

7.删除链表中重复的结点

题目描述

《双向带头循环链表及链表面试题二》

解题思路

1.对原链表进行判断,如果链表中没有节点或者只有一个节点,则不需要删除
2.给三个结构体指针prev,cur,next分别指向链表头的前一个,头,下一个,然后遍历链表prev用来保存cur的前一个,next往下走与cur中的值进行比较,当找出相等的值进行删除。不相等时三个指针进行遍历寻找。
3.需要注意的是,在删除节点时,重复的值可能有好几个,所以需要另一个指针del来保存cur,让cur指向下一个,对del进行删除,当cur指向next指针的位置说明这一部分的重复节点删除完毕。
然后next指针继续往后走,如果所有的节点被删除完,prev为空,则pHead=cur;否则prev往后走一步,如果next不为空,next也往后走一步,继续遍历。

程序部分

class Solution { 
public:
    ListNode* deleteDuplication(ListNode* pHead) 
    { 
        if(pHead==NULL||pHead->next==NULL)
        { 
            return pHead;
        }
        struct ListNode* prev=NULL;
        struct ListNode* cur=pHead;
        struct ListNode* next=pHead->next;
        while(next)
        { 
           if(cur->val==next->val)
           {    //next为空,和cur和next不相等时,循环结束
               //找next中与cur相等的节点
              while(next && cur->val==next->val)
              { 
                 next=next->next;
              }
               //将找到相等的节点,进行删除,当指针cur到了指针next的位置时
               //退出循环
              while(cur!=next)
              { 
                  struct ListNode* del=cur;
                  cur=cur->next;
                  free(del);
              }
               //表示prev后面的值被删完
              if(prev==NULL)
              { 
                  pHead=cur;
              }
              else
              {     //prev往后走一步
                  prev->next=cur;
              }
              if(next)
              {     //next往后走一步
                  next=next->next;
              }
           }
           else
           { //不等于三个指针往后遍历
            prev=cur;
            cur=next;
            next=next->next;
           }
        }
        return pHead;
    }
};

总结

将自己所学的东西进行纪录、总结,可能许多方面还需要完善,但作为刚刚上路的我会继续加油的!!!

    原文作者:工具人大刘
    原文地址: https://blog.csdn.net/qq_57770005/article/details/117093137
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞