苏州吴江建设局招投标网站,简历模板制作,长沙哪里做网站好,wordpress 站长统计插件第一题给定单链表的头节点 head #xff0c;将所有索引为奇数的节点和索引为偶数的节点分别组合在一起#xff0c;然后返回重新排序的列表。第一个节点的索引被认为是 奇数 #xff0c; 第二个节点的索引为 偶数 #xff0c;以此类推。请注意#xff0c;偶数组和奇数组内部…第一题给定单链表的头节点 head 将所有索引为奇数的节点和索引为偶数的节点分别组合在一起然后返回重新排序的列表。第一个节点的索引被认为是 奇数 第二个节点的索引为 偶数 以此类推。请注意偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。struct ListNode* oddEvenList(struct ListNode* head)
{if (head NULL){return head;}struct ListNode* odd head;//直接把奇数的第一个作为奇数组头节点struct ListNode* even head-next;//把偶数的第一个作为偶数组头节点struct ListNode* evenHead even;while (even ! NULL even-next ! NULL){odd-next even-next;odd odd-next;even-next odd-next;even even-next;}odd-next evenHead;把偶数组接在奇数组之后return head;}思考此处的even ! NULL even-next ! NULL能否调换答案是不可以因为此处通过的短路现象避免一些访问空指针的错误第二题将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if(list1NULL){return list2;}else if(list2NULL){return list1;}struct ListNode* newHeadlist1;struct ListNode* cur2list2;struct ListNode* cur1list1;if(list1-vallist2-val){newHeadlist2;cur2cur2-next;}else{cur1cur1-next;}struct ListNode* curnewHead;while(cur1!NULLcur2!NULL){if(cur1-valcur2-val){cur-nextcur1;curcur-next;cur1cur1-next;}else{cur-nextcur2;curcur-next;cur2cur2-next;}}if(cur1NULL){cur-nextcur2;}else{cur-nextcur1;}return newHead;
}本题主要是需要考虑情况完备以及新手在编程时一定不要吝啬于多创建一个常量进行记录能够让思路清晰很多当然本题也可以通过带哨兵位的链表当然思路大差不差时间复杂度也都是On空间复杂度依然为O1。struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ if (list1 NULL){return list2;}else if (list2 NULL){return list1;}struct ListNode* dummyHead malloc(sizeof(struct ListNode));dummyHead-val 0;struct ListNode* cur dummyHead, * cur1 list1, * cur2 list2;while (cur1 ! NULL cur2 ! NULL){if (cur1-val cur2-val){cur-next cur1;cur1 cur1-next;cur cur-next;}else{cur-next cur2;cur2 cur2-next;cur cur-next;}}if (cur1 ! NULL){cur-next cur1;}else if (cur2 ! NULL){cur-next cur2;}struct ListNode* ret dummyHead-next;free(dummyHead);return ret;
}第三题排序链表给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。方法一自顶向下归并排序对链表自顶向下归并排序的过程如下。第1步.找到链表的中间以中点为分界将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针快二慢一当快指针到达链表末尾时慢指针指向的链表节点即为链表的中点。对两个子链表分别排序。第2步.不断递归向下二分后对最小的两个子链表分别排序合并第3步.将最后两个排序后的子链表合并得到完整的排序后的链表。上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1即当链表为空或者链表只包含 1 个节点时不需要对链表进行拆分和排序。//合并函数因为递归的地方已经解决了传入链表为空的问题故可以不进行NULL的判断
struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) {struct ListNode* dummyHead malloc(sizeof(struct ListNode));dummyHead-val 0;struct ListNode *temp dummyHead, *temp1 head1, *temp2 head2;while (temp1 ! NULL temp2 ! NULL) {if (temp1-val temp2-val) {temp-next temp1;temp1 temp1-next;} else {temp-next temp2;temp2 temp2-next;}temp temp-next;}if (temp1 ! NULL) {temp-next temp1;} else if (temp2 ! NULL) {temp-next temp2;}return dummyHead-next;
}
//实现递归并终止的递归的函数
struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {if (head NULL) {return head;}if (head-next tail) {head-next NULL;return head;}struct ListNode *slow head, *fast head;while (fast ! tail) {slow slow-next;fast fast-next;if (fast ! tail) {fast fast-next;}}struct ListNode* mid slow;return merge(toSortList(head, mid), toSortList(mid, tail));
}//调用的排序函数
struct ListNode* sortList(struct ListNode* head) {return toSortList(head, NULL);
}时间复杂度O(nlogn)其中 n 是链表的长度。空间复杂度O(logn)其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。第四题给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val){if(headNULL){return NULL;}struct ListNode *dummyHead(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead-nexthead;struct ListNode*curdummyHead;//利用哨兵位避免传入空指针的情况而对下一个数据进行检索的写法。while(cur-next!NULL)//当遇到倒数第二个节点时 if else语句已经解决了尾数据是该删还是不该删{if(cur-next-valval){cur-nextcur-next-next;//跳过该节点指向下下个节点}else{curcur-next;//直接接入下一个数据若接入的是尾数据则跳出循环}}return dummyHead-next;
} 第五题给你单链表的头节点 head 请你反转链表并返回反转后的链表。*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){struct ListNode* dummyHeadmalloc( sizeof(struct ListNode) );struct ListNode*cur1head;struct ListNode*cur2NULL;//尾的next置为空while(cur1)//依次取下链表的数据连接在NULL上面{struct ListNode *tmpcur1-next;cur1-nextcur2;cur2cur1;cur1tmp;}return cur2;
}
