本章重點
鏈表OJ題
1. 刪除鏈表中等于給定值 val 的所有結(jié)點。 OJ鏈接
思路一：刪除頭結(jié)點時另做考慮（由于頭結(jié)點沒有前一個結(jié)點）
struct ListNode* removeElements(struct ListNode* head, int val) {
assert(head);
struct ListNode* cur = head;
struct ListNode* curPrev = NULL;
while (cur != NULL)
{
if (cur->val != val)
{
curPrev = cur;
cur = cur->next;
}
else
{
if (cur == head)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
curPrev->next = cur->next;
free(cur);
cur = curPrev->next;
}
}
}
return head;
}
思路二：添加一個虛擬頭結(jié)點，刪除頭結(jié)點就不用另做考慮
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
while (cur != NULL)
{
if (cur->val == val)
{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}
else
{
//尾插
if (tail == NULL)
{
newhead = tail = cur;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
}
if (tail)//如果最后一個數(shù)是要刪除的，tail就需要置空
tail->next = NULL;
return newhead;
}
2. 反轉(zhuǎn)一個單鏈表。OJ鏈接
思路：通過三個指針的操作，每次將當前節(jié)點反轉(zhuǎn)并向前移動
struct ListNode* reverseList(struct ListNode* head)
{
assert(head);
struct ListNode* n1, * n2, * n3;
n1 = NULL;
n2 = head;
n3 = n2->next;
while (n2)
{
//翻轉(zhuǎn)
n2->next = n1;
//交換
n1 = n2;
n2 = n3;
//記錄位置
if(n2 != NULL)
n3 = n3->next;
}
return n1;
}
?
思路：頭插法
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while (cur)
{
//保存cur下一個結(jié)點的位置
struct ListNode* next = cur->next;
//頭插
next = newhead;
newhead = cur;
//更新
cur = next;
}
return newhead;
}
3. 給定一個帶有頭結(jié)點 head 的非空單鏈表，返回鏈表的中間結(jié)點。如果有兩個中間結(jié)點，則 返回第二個中間結(jié)點。OJ鏈接
思路：快慢指針的前進方向相同，且它們步伐的「差」是恒定的，使用兩個指針變量，剛開始都位于鏈表的第 1 個結(jié)點，一個永遠一次只走 1 步，一個永遠一次只走 2 步，一個在前，一個在后，同時走。這樣當快指針走完的時候，慢指針就來到了鏈表的中間位置。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
?
4. 輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。OJ鏈接
首先讓快指針先行k步，然后讓快慢指針每次同行一步，直到快指針指向空節(jié)點，慢指針就是倒數(shù)第K個節(jié)點。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* fast = pListHead;
struct ListNode* slow = pListHead;
while (k--)//走k步
{
//鏈表沒有k步長，那么此時倒數(shù)就是空
if (fast == NULL)
return NULL;
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
?
5. 將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有結(jié)點組成的。OJ鏈接
思路一：我們可以用迭代的方法來實現(xiàn)上述算法。當 l1 和 l2 都不是空鏈表時，判斷 l1 和 l2 哪一個鏈表的頭節(jié)點的值更小，將較小值的節(jié)點添加到結(jié)果里，當一個節(jié)點被添加到結(jié)果里之后，將對應鏈表中的節(jié)點向后移一位。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
while (list1 && list2)
{
//小值給到新鏈表上
if (list1->val < list2->val)
{
if (tail == NULL)
{
newhead = tail = list1;
}
else
{
tail->next = list1;
tail = tail->next;
}
list1 = list1->next;
}
else
{
if (tail == NULL)
{
newhead = tail = list2;
}
else
{
tail->next = list2;
tail = tail->next;
}
list2 = list2->next;
}
}
if (list1)
tail->next = list1;
if (list2)
tail->next = list2;
return newhead;
}
?
思路二：哨兵位法，創(chuàng)建一個帶頭結(jié)點的鏈表，尾插的時候就不需要判斷鏈表是不是為空的尾插情況，最后再釋放哨兵位即可。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
struct ListNode* newhead = NULL;
struct ListNode* tail = NULL;
//哨兵位，方便尾插
newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while (list1 && list2)
{
//小值給到新鏈表上
if (list1->val < list2->val)
{
tail->next = list1;
tail = tail->next;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = tail->next;
list2 = list2->next;
}
}
if (list1)
tail->next = list1;
if (list2)
tail->next = list2;
struct ListNode* del = newhead;
newhead = newhead->next;
//釋放哨兵位
free(del);
return newhead;
}6. 編寫代碼，以給定值x為基準將鏈表分割成兩部分，所有小于x的結(jié)點排在大于或等于x的結(jié)點之前 。OJ鏈接
思路：首先創(chuàng)建四個節(jié)點lessHead,greaterHead,lessTail,greaterTail ，遍歷整個鏈表，比x小的尾插到lessHead為哨兵位的那個鏈表，比x大的尾插到greaterHead為哨兵位的那個鏈表，再把兩個鏈表連接起來 ，創(chuàng)建一個list節(jié)點指向這個鏈表 ，把greaterTail->next置空，避免成環(huán) ，釋放lessHead,greaterHead，返回list?
struct ListNode* partition(struct ListNode* pHead, int x)
{
struct ListNode* lessHead, * greaterHead;
lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* lessTail = lessHead;
struct ListNode* greaterTail = greaterHead;
struct ListNode* cur = pHead;
while (cur)
{
if (cur->val < x)
{
lessTail->next = cur;
lessTail = lessTail->next;
}
else
{
greaterTail->next = cur;
greaterTail = greaterTail->next;
}
cur = cur->next;
}
lessTail->next = greaterHead->next;
//此時greaterTail->next仍然鏈接初始鏈表的結(jié)點，需要置空，否則連環(huán)
greaterTail->next = NULL;
struct ListNode* newhead = lessHead->next;
free(lessHead);
free(greaterHead);
return newhead;
}
7. 鏈表的回文結(jié)構(gòu)。OJ鏈接
思路：先找到鏈表的中間結(jié)點，再把中間結(jié)點之后的逆序，和之前的鏈表比較值是否相等。
struct ListNode* middleNode(struct ListNode* head)//找中間結(jié)點
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)//反轉(zhuǎn)鏈表
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while (cur)
{
//保存cur下一個結(jié)點的位置
struct ListNode* next = cur->next;
//頭插
next = newhead;
newhead = cur;
//更新
cur = next;
}
return newhead;
}
bool chkPalindrome(struct ListNode* A) //查看值是否相等
{
struct ListNode* midnode = middleNode(A);
struct ListNode* reversemidnode = reverseList(midnode);
while (A && reversemidnode)
{
if(A->val != reversemidnode->val)
{
return false;
}
A = A->next;
reversemidnode = reversemidnode->next;
}
return true;
}
8. 輸入兩個鏈表，找出它們的第一個公共結(jié)點。OJ鏈接
思路：先計算兩個鏈表的長度，再讓較長的鏈表走差距步abs(lenA-LenB)長度，然后再依次比較是否相等。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA, * curB = headB;
//找尾結(jié)點 - 結(jié)點總數(shù)會少一個
int lenA = 1;//設置為1
int lenB = 1;//設置為1
while (curA->next)
{
curA = curA->next;
lenA++;
}
while (curB->next)
{
curB = curB->next;
lenB++;
}
//兩個鏈表不相交
if (curA != curB)
return NULL;
//找長鏈表
struct ListNode* LongList = headA, * ShortList = headB;
if (lenA < lenB)
{
LongList = headB;
ShortList = headA;
}
//長鏈表走絕對值（lenA - lenB）步
int count = abs(lenA - lenB);
while (count--)
{
LongList = LongList->next;
}
//同時向后走，相同就停下來
while (LongList != ShortList)
{
LongList = LongList->next;
ShortList = ShortList->next;
}
return ShortList;
}9. 給定一個鏈表，判斷鏈表中是否有環(huán)。OJ鏈接
思路：快慢指針，即慢指針一次走一步，快指針一次走兩步，兩個指針從鏈表其實位置開始運行， 如果鏈表 環(huán)則一定會在環(huán)中相遇，否則快指針率先走到鏈表的末尾。
bool hasCycle(struct ListNode *head) {
struct ListNode* fast = head ,* slow = head;
while(fast && fast->next)
{
fast = fast->next;
slow = slow->next->next;
if(fast == slow)
return true;
}
return false;
}
?為什么快指針每次走兩步，慢指針走一步可以？
- 假設鏈表帶環(huán)，兩個指針最后都會進入環(huán)，快指針先進環(huán)，慢指針后進環(huán)。當慢指針剛 進環(huán)時，可能就和快指針相遇了，最差情況下兩個指針之間的距離剛好就是環(huán)的長度。 此時，兩個指針每移動一次，快指針走兩次，慢指針走一次，之間的距離就縮小一步，直至最后差距為0，不會出現(xiàn)每次剛好是套圈的情況，因此：在滿指針走到一圈之前，快指針肯定是可以追上慢指針的，即相遇。
快指針一次走3步，走4步，...n步行嗎？
10. 給定一個鏈表，返回鏈表開始入環(huán)的第一個結(jié)點。 如果鏈表無環(huán)，則返回?NULL。OJ鏈接
思路一：一個指針從鏈表起始位置運行，一個指針從相遇點位置繞環(huán)，每次都走一步，兩個指針最終會在入口點的位置相遇
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast = head,*slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fase->next->next;
//相遇在環(huán)內(nèi)任意一個位置
if(slow == fast)
{
struct ListNode *meet = slow;
//兩結(jié)點關(guān)系L = (N-1) * C + C - X;
while(head != meet)
{
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}
?
?思路二：兩個指針相遇的地方的下一個結(jié)點置空，下一個結(jié)點位置和鏈表頭指針此時就可以轉(zhuǎn)為兩條鏈表求解公共點的問題。
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)//相交點
{
struct ListNode* curA = headA, * curB = headB;
//找尾結(jié)點 - 結(jié)點總數(shù)會少一個
int lenA = 1;//設置為1
int lenB = 1;//設置為1
while (curA->next)
{
curA = curA->next;
lenA++;
}
while (curB->next)
{
curB = curB->next;
lenB++;
}
//兩個鏈表不相交
if (curA != curB)
return NULL;
//找長鏈表
struct ListNode* LongList = headA, * ShortList = headB;
if (lenA < lenB)
{
LongList = headB;
ShortList = headA;
}
//長鏈表走絕對值（lenA - lenB）步
int count = abs(lenA - lenB);
while (count--)
{
LongList = LongList->next;
}
//同時向后走，相同就停下來
while (LongList != ShortList)
{
LongList = LongList->next;
ShortList = ShortList->next;
}
return ShortList;
}
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *fast = head,*slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fase->next->next;
//相遇在環(huán)內(nèi)任意一個位置
if(slow == fast)
{
struct ListNode *meet = slow;
struct ListNode *newhead = meet->next;
meet->next = NULL;
return getIntersectionNode(head,newhead);
}
}
return NULL;
}11.給定一個鏈表，每個結(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何結(jié)點或空結(jié)點。 要求返回這個鏈表的深度拷貝。OJ鏈接
思路：迭代 + 節(jié)點拆分
方法：
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
while(cur)
{
struct Node* next = cur->next;
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
//插入
cur->next = copy;
copy->next = next;
//往后走
cur = next;
}
cur = head;
while(cur)
{
struct Node* copy = cur->next;
//置 copy random
if(cur->random == NULL)
copy->random = NULL;
else
copy->random = cur->random->next;
cur = copy->next;
}
cur = head;
struct Node* copyhead = NULL,*cpoytail = NULL;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
//copy結(jié)點尾插到新鏈表
if(cpoytail == NULL)
{
copyhead = copytail = copy;
}
else
{
copytail->next = copy;
copytail = copytail->next;
}
//恢復原鏈表
cur->next = next;
cur = next;
}
return copyhead;
}
?本章結(jié)束啦?。?！文章來源：http://www.zghlxwxcb.cn/news/detail-677759.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-677759.html
到了這里，關(guān)于【編織時空三：探究順序表與鏈表的數(shù)據(jù)之旅】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
