网站设计基本要求,建立购物网站,哪里找人做网站,物流网站建设计划书目录 1. 单链表相关练习题1.1 移除链表元素1.2 反转链表1.3 链表的中间结点1.4 链表的倒数第k个结点1.5 合并两个有序链表1.6 链表分割1.7 链表的回文结构1.8 相交链表1.9 判断一个链表中是否有环1.10 寻找环状链表相遇点1.11 链表的深度拷贝 1. 单链表相关练习题 注#xff1… 目录 1. 单链表相关练习题1.1 移除链表元素1.2 反转链表1.3 链表的中间结点1.4 链表的倒数第k个结点1.5 合并两个有序链表1.6 链表分割1.7 链表的回文结构1.8 相交链表1.9 判断一个链表中是否有环1.10 寻找环状链表相遇点1.11 链表的深度拷贝 1. 单链表相关练习题 注单链表结构上存在一定缺陷所以链表相关的题目一般都针对与单链表。 1.1 移除链表元素 题目要求 题目信息 头节点head移除值val 题目链接 移除链表元素 方法顺序处理法 思路分析链表结构与结点所处的位置是否为空链表结点是否为头结点分情况依次处理。 过程演示
struct ListNode* removeElements4(struct ListNode* head, int val)
{struct ListNode* pre NULL;struct ListNode* cur head;while (cur){if (cur-val val){//头删if (cur head){head head-next;free(cur);cur head;}else//中间删{pre-next cur-next;free(cur);cur pre-next;}}else{pre cur;cur cur-next;}}return head;
}1.2 反转链表 题目要求 题目链接 反转链表 过程演示
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* pre NULL;struct ListNode* mid head;struct ListNode* cur NULL;if(head){cur head-next;}while(mid){mid-next pre;pre mid;mid cur;if(cur){cur cur-next;}}return pre;}1.3 链表的中间结点 题目要求 题目链接 链表的中间结点 过程演示快慢指针法
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fast head;struct ListNode* slow head;while(fast ! NULL fast-next ! NULL){fast fast-next-next;slow slow-next;}return slow;
}1.4 链表的倒数第k个结点 题目要求 题目链接 倒数第k个结点 过程演示
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* cur pListHead;struct ListNode* pre pListHead;while(cur k--){cur cur-next;}if(k 0){pre NULL;}while(cur){pre pre-next;cur cur-next;}return pre;
}1.5 合并两个有序链表 题目要求 题目链接 合并两个链表 struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* newhead NULL;struct ListNode* cur NULL;struct ListNode* newnode NULL;if(list1 NULL)return list2;if(list2 NULL)return list1;while(list1 ! NULL list2 ! NULL){if(list1-val list2-val){newnode list1;list1 list1-next;}else{newnode list2;list2 list2-next;}if(newhead NULL){newhead newnode;newnode-next NULL;cur newhead;}else{//在遍历过程中list1 或 list2 会等于 NULLcur-next newnode;if(newnode ! NULL){newnode-next NULL;cur cur-next;}}}//有一个链表本就为空if(list1){cur-next list1;}if(list2){cur-next list2;}return newhead;
}1.6 链表分割 题目要求 题目链接 合并两个链表 ListNode* BuyNewNode(int val){ListNode* newnode (ListNode*)malloc(sizeof(ListNode));newnode-val val;newnode-next nullptr;return newnode;}ListNode* partition(ListNode* pHead, int x) {ListNode* newhead1 nullptr;ListNode* end1 nullptr;ListNode* newhead2 nullptr;ListNode* end2 nullptr;ListNode* cur pHead;while(cur){if(cur-val x){if(newhead1 nullptr){newhead1 BuyNewNode(cur-val);end1 newhead1; }else {end1-next BuyNewNode(cur-val);end1 end1-next;}}else {if(newhead2 nullptr){newhead2 BuyNewNode(cur-val);end2 newhead2; }else {end2-next BuyNewNode(cur-val);end2 end2-next;}}cur cur-next;}if(newhead1 nullptr){newhead1 newhead2;}else {end1-next newhead2;}return newhead1;}1.7 链表的回文结构 题目要求 题目链接 回文串 ListNode* reverse(ListNode* head){ListNode* pre nullptr;ListNode* mid head;ListNode* cur head-next;while (mid){mid-next pre;pre mid;mid cur;if (cur){cur cur-next;}}return pre;}bool chkPalindrome(ListNode* A){//找相同逆置//逐点比较//回文结构存在奇数个结点//获取中间结点ListNode* fast A;ListNode* slow A;while(fast fast-next){fast fast-next-next;if(fast){slow slow-next;}}//表1ListNode* newhead2 slow-next;//表2slow-next nullptr;ListNode* newhead1 reverse(A);if(fast){newhead1 newhead1-next;}while (newhead1 newhead2 newhead1-val newhead2-val){newhead1 newhead1-next;newhead2 newhead2-next;}if (newhead1 nullptr newhead2 nullptr){return true;}return false;}1.8 相交链表 题目要求 题目链接 相交链表 void swap(struct ListNode** node1, struct ListNode** node2)
{struct ListNode* tmp *node1;*node1 *node2;*node2 tmp;
}struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* short_list1 headA;struct ListNode* short_list2 headA;struct ListNode* long_list1 headB;struct ListNode* long_list2 headB;while(short_list1 long_list1){short_list1 short_list1-next;long_list1 long_list1-next;}if(short_list1){swap(short_list1, long_list1);swap(short_list2, long_list2);}while(long_list1){long_list1 long_list1-next;long_list2 long_list2-next;}//while((short_list2 long_list2) || short_list2 ! long_list2)while(short_list2 long_list2 short_list2 ! long_list2){long_list2 long_list2-next;short_list2 short_list2-next;}return short_list2;
}1.9 判断一个链表中是否有环 题目要求 题目链接 判断是否有环 //逻辑步骤存疑
bool hasCycle(struct ListNode *head)
{struct ListNode* fast head;struct ListNode* slow head;//err: while(fast slow ! fast)while(fast fast-next){fast fast-next-next;slow slow-next;if(slow fast){return true;}}return false;
}1.10 寻找环状链表相遇点 题目要求 题目链接 寻找环状链表相遇点 思路依靠结论一个结点从起始点一个结点从相遇点快慢指针相遇点以同速行走一次走一步当他们再一次初次相遇时此相遇结点即为入环点。 struct ListNode *detectCycle(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){break;}}//判断是否为环状链表if(fast NULL || fast-next NULL){return NULL;}slow head;while(fast ! slow){fast fast-next;slow slow-next;}return fast;
}1.11 链表的深度拷贝 题目要求 题目链接 链表的深度拷贝 //思路
//生成拷贝结点
//调整拷贝结点的指针
//还原原链表链接拷贝结点
struct Node* BuyNewNode(int val)
{struct Node* newnode (struct Node*)malloc(sizeof(struct Node));newnode-val val;newnode-next NULL;newnode-random NULL;return newnode;
}struct Node* copyRandomList(struct Node* head)
{struct Node* node1 head;//判断是否为空链表if(head NULL){return head;}//创建新节点while (node1){struct Node* newnode BuyNewNode(node1-val);newnode-next node1-next;node1-next newnode;node1 node1-next-next;}//调整新节点的随机指针struct Node* node2 head-next;node1 head;while (node2){if (node1-random){node2-random node1-random-next;}node1 node1-next-next;if (node2-next){node2 node2-next-next;}else{node2 node2-next;}}//还原链表链接新链表node1 head;node2 head-next;struct Node* newhead head-next;while (node1){node1-next node1-next-next;if (node2-next){node2-next node2-next-next;}node1 node1-next;node2 node2-next;}return newhead;
}
