8.29 leetcode刷题

链表题型：
206 反转链表：
循环：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prior=nullptr,*cur=head,*next;
        while(cur){
            next=cur->next;
            cur->next=prior;
            
            prior=cur;
            cur=next;
        }
        
        return prior;
    }
};

递归：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)
            return nullptr;
        ListNode *first=head;
        if(first->next==nullptr)
            return first;
        ListNode *second=reverseList(first->next);        
        head->next->next=head;
        head->next=nullptr;
        return second;
    }
};

思路：
可以利用循环或者递归解决，递归代码简短，思路清晰，但是性能不如循环。
递归的窍门是联系数学归纳法，找到n-1和n的关系。
循环 则要注意循环不定式，维持不变量，迭代不变量。

最后解释下递归的思路：
递归的话先考虑函数的作用和参数，作用是反转链表，参数是链表头结点。那么开始进行递归过程的设计。我们要找的是头节点el(n)和去点头结点之后的链表之间f(n-1）的联系,考虑一下要怎么根据f(n-1)和el(n)去找到f(n)。

设计思路是：
令f(n-1)的尾指针（head->next）指向head，然后令head->next==nullptr（重要，否则会造成死循环）
然后开始从头到尾进行检查，剔除非法情况。
设计递归终止条件（head==nullptr）

---

练习题：92 83 86 328 2 455

---

虚拟头结点法（解决删除元素时头结点的问题）
203 移除链表元素

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *dummy=new ListNode(0);
        dummy->next=head;
        ListNode *cur=dummy;
        while(cur->next){
            if(cur->next->val==val){
                ListNode *tar=cur->next;
                cur->next=tar->next;
                delete tar;
            }
            else
                cur=cur->next;
        }
        head=dummy->next;
        delete dummy;
        return head;
    }
};

---

练习：82 21

---

24 成对交换链表节点

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *dummy=new ListNode(0);
        dummy->next=head;
        ListNode *prior=dummy,*t1=head,*t2,*next;
        while(t1 && t1->next){
            t2=t1->next;
            next=t2->next;
            
            t1->next=next;
            t2->next=t1;
            prior->next=t2;
            
            prior=t1;
            t1=next;
        }
        
        head=dummy->next;
        delete dummy;
        return head;
    }
};

思路：
因为交换涉及到了头结点的变动，所以要使用虚拟头结点的方法。
另外因为链表不支持随机访问，所以申请了多个指针去操作需要操作的4个元素，起到了随机访问的用途

---

练习：25 147 148

---

237 删除链表中的一个节点

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        ListNode *tar=node->next;
        node->next=tar->next;
        delete tar;
    }
};

19 删除链表中倒数第n个节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy=new ListNode(0);
        dummy->next=head;
        ListNode *fast=dummy,*slow=dummy;
        for(int i=0;i<=n;i++){
            fast=fast->next;
        }
        while(fast){
            slow=slow->next;
            fast=fast->next;
        }
        
        ListNode *tar=slow->next;
        slow->next=tar->next;
        delete tar;
        
        head=dummy->next;
        delete dummy;
        return head;
    }
};

思路：
快慢指针法 + 虚拟头结点法

首先因为head节点可能变化，而且涉及删除，所以使用了虚拟头结点法来处理这些情况
快慢指针法是为了定位我们要删除哪个节点。
难点是快指针要走多少步，因为我们引入了虚节点，而且为了实现删除功能，我们希望定位的是待删除节点的前一个节点，所以快指针应该先走n+1步才能达到目的（可以举个例子想象一下）

---

练习：61 143 234

---