备战秋招——算法与数据结构（7）

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

参考回答：

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表。