循环链表的实现及链表面试题二
链表
循环链表的实现
双向带头循环链表的优越性
双向循环链表：有两个指针，一个指向前一个节点，一个指向后一个节点。
值得注意的是双向带头循环链表为空时，两个指针指向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;
}
};
总结
将自己所学的东西进行纪录、总结，可能许多方面还需要完善，但作为刚刚上路的我会继续加油的！！！