19. Remove Nth Node From End of List 刪除鏈表的倒數(shù)第N個(gè)結(jié)點(diǎn)
例如 給出列表: 1->2->3->4->5, and n = 2.
刪除倒數(shù)第二個(gè)結(jié)點(diǎn)后變?yōu)椋?->2->3->5
題目限定n總是有效的诬辈，且要求我們盡量用一次遍歷解決問題
數(shù)據(jù)結(jié)構(gòu)：Linked List
算法技巧：Tow Pointers（輔助指針）
//總體思路是設(shè)置兩個(gè)指針A和B磅轻，A指向head結(jié)點(diǎn)递鹉，B先走2步指向2結(jié)點(diǎn)。然后AB指針同時(shí)向后移動(dòng)乍楚，直到B指針為空，這時(shí)A指針指向的是倒數(shù)第三個(gè)結(jié)點(diǎn)2喂急，執(zhí)行常規(guī)刪除動(dòng)作
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head->next)
return NULL;
ListNode* pre = head;
ListNode *cur = head;
//B指針先走2步
for(int i = 0; i < n; ++i)
cur = cur->next;
if(!cur)
return head->next;
//AB指針同時(shí)向后移動(dòng)止邮，直到B指針為空
while(cur->next)
{
cur = cur->next;
pre = pre->next;
}
//常規(guī)刪除結(jié)點(diǎn)操作
pre->next = pre->next->next;
return head;
}
};
206. Reverse Linked List 反轉(zhuǎn)單鏈表
使用到的數(shù)據(jù)結(jié)構(gòu)：List
使用到的算法技巧：dummy node（虛擬結(jié)點(diǎn)）
//引入虛擬結(jié)點(diǎn)dummy，讓reverse過(guò)程更好理解
//反轉(zhuǎn)流程：1->2->3->4->5->NULL
//step1 dummy node(-1)->1->2->3->4->5->NULL cur(1)
//step2 dummy node(-1)->2->1->3->4->5->NULL cur(1)
//step3 dummy node(-1)->3->2->1->4->5->NULL cur(1)
//step4 dummy node(-1)->4->3->2->1->5->NULL cur(1)
//step5 dummy node(-1)->5->4->3->2->1->NULL cur(1)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head) return head;
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = head;
while(cur->next)
{
ListNode* tmp = cur->next;
cur->next = tmp->next;
tmp->next = dummy->next;
dummy->next = tmp;
}
return dummy->next;
}
};
怎樣應(yīng)對(duì)IT面試與筆試-（一）
怎樣應(yīng)對(duì)IT面試與筆試-（二）
怎樣應(yīng)對(duì)IT面試與筆試-（三）
怎樣應(yīng)對(duì)IT面試與筆試-（四）
怎樣應(yīng)對(duì)IT面試與筆試-（五）
怎樣應(yīng)對(duì)IT面試與筆試-（五-1）
怎樣應(yīng)對(duì)IT面試與筆試-（六）
怎樣應(yīng)對(duì)IT面試與筆試-（七）
怎樣應(yīng)對(duì)IT面試與筆試-（八）
怎樣應(yīng)對(duì)IT面試與筆試-（九）
怎樣應(yīng)對(duì)IT面試與筆試-（十）
怎樣應(yīng)對(duì)IT面試與筆試-（十一）
怎樣應(yīng)對(duì)IT面試與筆試-（十二）
怎樣應(yīng)對(duì)IT面試與筆試-（十三）
怎樣應(yīng)對(duì)IT面試與筆試-（十四）
怎樣應(yīng)對(duì)IT面試與筆試-（十五）
怎樣應(yīng)對(duì)IT面試與筆試-（十六）
