剑指offer刷题

方法1：递归方式

//方法1.递归函数
class Solution {
public:
    //递归函数
    void recursion(ListNode* head, vector& res){
        if(head != nullptr){//边界条件
            //先往链表深处遍历
            recursion(head->next, res);
            //再填充到数组就是逆序
            res.push_back(head->val);
        }
    }
    vector printListFromTailToHead(ListNode* head) {
        vector res;
        //递归函数打印
        recursion(head, res);
        return res;
    }
};

//方法2.栈
class Solution {
public:
    vector reversePrint(ListNode* head) {
        vector res;
        stack s;
        while(head){
            //入栈
            s.push(head->val);
            head=head->next;
        }
        while(!s.empty()){
            //出栈
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};

 //方法1递归函数
class Solution {
public:
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //当一个链表递归到尾部时，返回另一个还未递归到尾部的链表
        if(!l1){           
            return l2;
        }
        if(!l2){
            return l1;
        }
        if(l1->val>l2->val){
            l2->next=mergeTwoLists(l1,l2->next);
            return l2;
        }
        l1->next=mergeTwoLists(l1->next,l2);
        return l1;
    }
};

//方法2迭代方法
class Solution {
public:
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //设置dummy伪头结点（哨兵节点）
        ListNode*dummy=new ListNode(0),*node=dummy;
        while(l1&&l2){
            if(l1->val>l2->val){
                node->next=l2;
                l2=l2->next;
            }
            else{
                node->next=l1;
                l1=l1->next;
            }
            //更新node
            node=node->next;
        }
        //node下一跳接不是尾节点的链表
        node->next=l1?l1:l2;
        return dummy->next;
    }
};

链表 headA 和headB 的长度分别是 m 和 n。假设链表headA 的不相交部分有 a 个节点，链表headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m，b+c=n。

• 如果 a=b，则两个指针会同时到达两个链表的第一个公共节点，此时返回两个链表的第一个公共节点；
• 如果 a ≠ neq ​=b，则指针pA 会遍历完链表 headA，指针pB 会遍历完链表headB，两个指针不会同时到达链表的尾节点，然后指针 pA 移到链表headB 的头节点，指针pB 移到链表headA 的头节点，然后两个指针继续移动，在指针pA 移动了a+c+b 次、指针pB 移动了 b+c+a 次之后，两个指针会同时到达两个链表的第一个公共节点，该节点也是两个指针第一次同时指向的节点，此时返回两个链表的第一个公共节点。

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        ListNode* l1=pHead1,* l2=pHead2;
        while(pHead1!=pHead2){         
            pHead1=pHead1?pHead1->next:l2;
            pHead2=pHead2?pHead2->next:l1;
        }
        return pHead1;
    }
};

对于1.链表找环路2.倒数最后k个节点的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。
概括一下：
根据：

• f=2s （快指针每次2步，路程刚好2倍）
• f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast=pHead,*slow=pHead;
//         if(!fast) return fast;
//         while(fast->next&&fast->next->next){
//             fast=fast->next->next;
//             slow=slow->next;
//             if(fast==slow) break;
//         }
//         if(!fast->next||!fast->next->next) return NULL;
        //简化代码
        do{
            if(!fast||!fast->next) return nullptr;
            fast=fast->next->next;
            slow=slow->next;
        }while(fast!=slow);
        fast=pHead;
        while(fast!=slow){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};

快慢指针：
快慢指针的思想。我们将第一个指针fast 指向链表的第k+1 个节点，第二个指针slow 指向链表的第一个节点，此时指针fast 与slow 二者之间刚好间隔 k 个节点。此时两个指针同步向后走，当第一个指针fast 走到链表的尾部空节点时，则此时slow 指针刚好指向链表的倒数第k个节点。

• 我们首先将fast 指向链表的头节点，然后向后走 k 步，则此时 fast 指针刚好指向链表的第k+1 个节点。
• 我们首先将slow 指向链表的头节点，同时 slow 与fast 同步向后走，当 fast 指针指向链表的尾部空节点时，则此时返回 slow 所指向的节点即可。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast=head,*slow=head;
        for(int i=0;i
            if(!fast) return nullptr;
            fast=fast->next;
        }
        while(fast){
            fast=fast->next;
            slow=slow->next;
        }
        return slow;
    }
};

参考LeetCode题解

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return nullptr;
        Node* cur=head;
        unordered_map hash;
        while(cur){
            hash[cur] = new Node(cur->val);
            cur=cur->next;
        }
        cur=head;
        while(cur){
            hash[cur]->next=hash[cur->next];
            hash[cur]->random=hash[cur->random];
            cur=cur->next;
        }
        return hash[head];
    }
};