<>● 请你手写代码,如何合并两个有序链表

参考回答:
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL) { return l2; } if(l2 == NULL) { return l1; } if(l1->val < l2->val
) { l1->next=mergeTwoLists(l1->next,l2); return l1; } else { l2->next=
mergeTwoLists(l1,l2->next); return l2; } } };
<>● 手写代码:反转链表

参考回答:
Void reversal_list(mylist * a_list) { mylist * forward_node = nullptr; mylist
* cur_node= a_list->next; mylist* next_node = cur_node->next; if(cur_node ==
nullptr) { return ; } while(1) { cur_node->next = forward_node; forward_node =
cur_node; cur_node = next_node; if(cur_node == nullptr) { break; } next_node =
cur_node->next; } a_list->next = forward_node; }
<>● 判断一个链表是否为回文链表,说出你的思路并手写代码

参考回答:

思路:使用栈存储链表前半部分,然后一个个出栈,与后半部分元素比较,如果链表长度未知,可以使用快慢指针的方法,将慢指针指向的元素入栈,然后如果快指针指向了链表尾部,此时慢指针指向了链表中间
bool is_palindromic_list2(mylist *a_list) { if(a_list == nullptr) { return
false; } stack<int>list_value; mylist * fast =a_list; mylist *slow =a_list;
while(fast->next!=nullptr && fast->next->next!=nullptr) { list_value.push(slow->
next->value); slow = slow->next; fast = fast->next->next; } cout<<"middle elem
value is "<<slow->next->value<<endl; if(fast->next != nullptr) { cout<<"the
list has odd num of node"<<endl; slow =slow->next; } int cur_value; while(!
list_value.empty()) { cur_value = list_value.top(); cout<<"stack top value is"<<
cur_value<<endl; cout<<"list value is "<<slow->next->value<<endl; if(cur_value
!= slow->next->value) { return false; } list_value.pop(); slow = slow->next; }
return true; }
<>● 请你手写链表反转

参考回答
struct ListNode { int val; struct ListNode *next; ListNode(int x) :val(x), next
(NULL) {} } ListNode* ReverseList(ListNode* pHead) { if(!pHead||!pHead->next)
return pHead; ListNode *pre=nullptr; ListNode *p=pHead; ListNode *next=pHead->
next; while(p) { p->next=pre; pre=p; p=next; if(next) next=next->next; } return
pre; }
<>● 请问什么是单向链表,如何判断两个单向链表是否相交

参考回答:
考察点:数据结构,算法
公司:百度

1、单向链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点。

列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。

2、判断两个链表是否相交

1)方法1:

链表相交之后,后面的部分节点全部共用,可以用2个指针分别从这两个链表头部走到尾部,最后判断尾部指针的地址信息是否一样,若一样则代表链表相交!

2)方法2:

可以把其中一个链表的所有节点地址信息存到数组中,然后把另一个链表的每一个节点地址信息遍历数组,若相等,则跳出循环,说明链表相交。进一步优化则是进行hash排序,建立hash表。

技术
©2019-2020 Toolsou All rights reserved,
[RK3399][Android7.1] 学习笔记 DRM驱动程序开发(介绍)(精华)2020年8月13日 C#基础知识点 windform实现双色球Hackbar 使用教程线上问题排查之HTTP状态码——415和406在Vue中使用Web Worker【Python】读取txt文件,获取指定行中指定位置数据(精华)2020年7月13日 微信小程序 页面间通信使用VS2019 “Windows桌面应用程序”模块创建Win32窗口(精华)2020年6月26日 C#类库 Enum(扩展方法)最优化方法总结:公式解、数值优化、求解思想