演算法訓練營
- 核心考點：鏈表操作，思維縝密程度
- 核心考點：鏈表合并
- 核心考點：鏈表操作，臨界條件檢查，特殊情況處理
核心考點：鏈表操作，思維縝密程度
解題思路：
定義三個指標，整體右移，邊移動，邊翻轉，保證不會斷鏈，這里我們要注意分別只有一個節點，兩個節點和多個節點的情況，
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if (pHead == NULL || pHead->next == NULL)
{
return pHead;
}
ListNode* first = pHead;
ListNode* second = first->next;
ListNode* third = second->next;
while (third){
//翻轉
second->next = first;
//指標整體后移
first = second;
second = third;
third = third->next;
}
second->next = first;//當傳入的鏈表只有兩個節點或者上述翻轉結束最后一個并沒有翻轉
pHead->next = nullptr;
pHead = second;
return pHead;
}
};
核心考點：鏈表合并
解題思路：
在一個鏈表中插來插去比較混亂，這里我們定義一個新的鏈表，將資料往里插，
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* merge(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//申請一個頭結點
struct ListNode* tail = guard;//尾指標
struct ListNode* cur1 = l1;//記錄當前遍歷到的l1鏈表的結點位置
struct ListNode* cur2 = l2;//記錄當前遍歷到的l2鏈表的結點位置
while (cur1&&cur2)//當l1，l2中有一個鏈表遍歷完畢時便停止
{
//取小的結點尾插到新鏈表后面
if (cur1->val < cur2->val)
{
tail->next = cur1;
cur1 = cur1->next;
}
else
{
tail->next = cur2;
cur2 = cur2->next;
}
tail = tail->next;//結點增加，尾指標后移
}
//將未遍歷完的鏈表的剩余結點接到新鏈表后面
if (cur1)
tail->next = cur1;
else
tail->next = cur2;
struct ListNode* head = guard->next;
free(guard);
return head;
}
核心考點：鏈表操作，臨界條件檢查，特殊情況處理
解題思路
通過快慢指標的方式，進而達到去重的結果這里要考慮特別多的特殊情況，如：全部相同，全部不相同，部分相同等，為了方便解題我們定義頭結點，主要是應對全部，相同的情況，
class Solution {
public:
ListNode* deleteDuplication(ListNode* pHead) {
if (pHead == NULL)
{
return pHead;
}
ListNode* head = new ListNode(0);
head->next = pHead;
ListNode* prev = head;
ListNode* last = prev->next;
while (last!=NULL)
{
//1.確立重復區域的起始位置
while (last->next != NULL&&last->val != last->next->val)
{
prev = last;
last = last->next;
}
//2.確立重復區域
while (last->next != NULL&&last->val == last->next->val)
{
last = last->next;
}
if (prev->next != last)
{
prev->next = last->next;
}
last = last->next;
}
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298659.html
標籤：其他
上一篇：LeetCode 145. 二叉樹的后序遍歷【c++/java詳細題解】
下一篇：MEMZ病毒詳細分析