广西钦州住房与城乡建设局网站,珠海易注册网站,成都高新区规划建设局网站,网站设计需要哪些技能题目 链表的中间结点原题入口题目内容题目解析思路一代码实现一思路二代码实现二 链表中倒数第k个结点题目链接题目内容思路代码实现 合并两个有序链表原题入口题目内容思路代码实现 反转链表题目传送入口题目内容思路一代码复现一思路二代码实现二 链表的中间结点
原题入口
… 题目 链表的中间结点原题入口题目内容题目解析思路一代码实现一思路二代码实现二 链表中倒数第k个结点题目链接题目内容思路代码实现 合并两个有序链表原题入口题目内容思路代码实现 反转链表题目传送入口题目内容思路一代码复现一思路二代码实现二 链表的中间结点
原题入口
题目内容 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 题目解析 该题我们选择一次遍历返回中间结点,可以选择两次遍历,只是时间复杂度变大了,这里介绍比较优的解法 思路一 该思路利用快慢指针的方法,快指针一次跳两个结点,慢指针一次跳一个结点,来实现中间的效果,此处中间的思想有了头绪,那么结束循环的条件又是我们要考虑的了,如果是奇数个结点,fast在最后一个结点停止,最后一个结点的next才等于NULL,奇数的结束条件是fast-nextNULL;就偶数而言,结束条件就是NULL 代码实现一
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* fasthead,* slowhead;//可以简化代码,把slow去除,直接替换为headwhile(fastfast-next){slowslow-next;fastfast-next-next;}return slow;
}思路二 核心思想是使用两个计数器 count 和 ret通过遍历链表找到中间位置的节点。其中通过判断 count / 2 1 ret 来确定是否为中间位置。这样当循环结束时head 指向的节点即为链表的中间节点。 代码实现二
struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* tem head;int count 1,ret 1;while(tem){ if(count/21ret){headhead-next;ret;}count; temtem-next;}return head;
}链表中倒数第k个结点
题目链接
题目内容
输入一个链表输出该链表中倒数第k个结点。
思路 快慢指针的思想,先让快指针走k步,然后快慢指针同时走,注意判断快指针是否越界 代码实现
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{struct ListNode* p1pListHead,* p2pListHead;while(k--){if(p1NULL) return NULL;p1p1-next;}while(p1){p2p2-next;p1p1-next;}return p2;
}合并两个有序链表
原题入口
题目内容 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 思路 类似两个有序数组合并,先考虑空链表的情况,再通过遍历两个有序链表一次逐个比较节点的值将较小的节点连接到合并链表中最终得到合并后的有序链表。 代码实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head NULL,* tail NULL;if(list1NULL) return list2;if(list2NULL) return list1;while(list1list2){if(list1-vallist2-val){if(headNULL){headtaillist2;}else{tail-nextlist2;tailtail-next;}list2list2-next;}else {if(headNULL){headtaillist1;}else{tail-nextlist1;tailtail-next;} list1list1-next;}}if(list1)tail-nextlist1;if(list2)tail-nextlist2;return head;
}反转链表
题目传送入口
题目内容 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 思路一 在遍历链表的过程中,改变结点指向的方向,原题实例,如果将2的next指向1的话,你就丢失2之后的结点,所以我们要用3个指针**,前两个指针改变导向,第三个指针记录第二个指针的下一个位置** 代码复现一
struct ListNode* reverseList(struct ListNode* head)
{ if(headNULL) return NULL;struct ListNode* p1 NULL;struct ListNode* p2 head;struct ListNode* p3 head-next;while(p2){p2-next p1;p1p2;p2p3;if(p3)p3p3-next;}return p1;
}思路二 第二种思路与第一种比较相似,第二种采用尾插的方法来进行结点的逐个插入,仍旧采用三指针,前两个指针对结点尾插,第三个结点记录下一个结点的位置,防止失去与原链表的关联 代码实现二
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* rhead NULL, * cur head;while (cur){struct ListNode* next cur-next;cur-next rhead;rhead cur;cur next;}return rhead;
}
