● 請你手寫代碼，如何合并兩個有序連結清單
參考回答：
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表。