剑指offer之链表

剑指 Offer 52. 两个链表的第一个公共节点

题目分析：

我们要在两个链表中找到第一个公共的节点，采用双指针法来实现。我们

         p1先遍历headA，然后遍历headB

          p2 先遍历headB，然后遍历headA

          要是有重合的节点，他们就会相遇

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        
        ListNode* p1 = headA;
        ListNode* p2 = headB;
        /*p1先遍历headA，然后遍历headB
          p2 先遍历headB，然后遍历headA
          要是有重合的节点，他们就会相遇*/
        while(p1 != p2){
 
            if(p1)  p1 = p1 -> next;
            else   p1 = headB;
             
             
            if(p2)  p2 = p2 -> next;
            else   p2 = headA;
            
        }
        return p1;//返回我们共同节点的节点的指针
        
    }
};

剑指 Offer 06. 从尾到头打印链表https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

题目分析：

就是怎么把链表倒着打印输出

1、使用insert函数倒着插入

2、使用容器的算法将容器倒着输出

3、将数据存放到栈里面，然后就可以实现倒着打印

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        
        vector<int> v1;
      
        
          while(head){
 
           v1.insert(v1.begin(),head->val);//在v1.begin()位置之前插入字符head—>val，这样就是倒序
 
           head = head ->next;
 
          }
        
            return v1;
            
        }   
};

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        
        vector<int> v1;
      
        
          while(head){
 
           v1.push_back(head->val);
 
           head = head ->next;
 
          }
        
            return vector<int>(v1.rbegin(),v1.rend());//将容器倒着输出rbegin，rend就是倒序的意思
            
        }   
};

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        
        vector<int> v1;
        stack<int>stk;//创建一个栈的容器
 
          while(head){
 
           stk.push(head ->val);//元素入栈
           head = head ->next;
 
          }
          int len = stk.size();
          for( int i = 0; i<len;i++){
              v1.push_back(stk.top());//将栈顶元素后插进容器中
              stk.pop();
          }
           return v1;
            
            
        }   
};

剑指 Offer 22. 链表中倒数第k个节点https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

题目分析：

需要我们找到链表的倒数第k个元素，这样我们可以使用双指针法，让两个指针之间的距离相差k个单位，等我们远处的指针指向了链表尾部空的位置，我们近处的指针就是倒数第k个单位

//front与later之间的距离是k，倒数的话就是我们后指针指向空，这样前后指针指向最后k个
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* front = head;//近处指针
        ListNode* later = head;//远处指针
        while (k-- && front != NULL) 
            front= front->next; // front1 先移动k位
        while (front != NULL) { // front与 later同时移动，直到later指向尾端
            front = front->next;
            later =  later->next;
        }
        return later; // 此时later 就是第k个节点起始位置
    }
};

剑指 Offer 24. 反转链表https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/

题目分析：

我们只需要将指针指向的方向反过来就可以实现

我们需要将cur指针指向的节点间的指针反向，因为我们cur指针已经被破坏，不能指针利用前进，只能将下一个节点的地址保存起来

 

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
         ListNode* pre = nullptr;
         ListNode* cur =head;
         
        while(cur){
        ListNode*later = cur ->next;
        cur->next = pre;//指针反转
        pre = cur;
        cur = later;
        }
        return pre;
 
    }
};

21. 合并两个有序链表https://leetcode.cn/problems/merge-two-sorted-lists/

题目解析：

我们就好比是球球大作战里面的一个大球，我们面对有两个队伍，先判断哪个队伍前面的最小，就去吃那个，在两个队伍之间反复横跳，吃我一个我们就变胖一些，就这样一直吃完两个队伍

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);.//吃货节点preHead
 
        ListNode* prev = preHead;
        //当两条链表都存在的情况下
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;//l1的现节点指针移动
            } else {
                prev->next = l2;//新链表的当前节点指针指向l2
                l2 = l2->next;//l2的现节点指针移动
            }
            prev = prev->next;//吃掉一个节点
        }
        //下面是只剩下一条或者一条都没有
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;//     l1为空的话第三条的指针就指向l2的剩余部分，反之亦然
 
        return preHead->next;//返回第三条链表的第二个节点
    }
};

剑指 Offer 35. 复杂链表的复制https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/

题目分析：

要复制出一个链表

1、在原来链表的节点之后创建一个空间，并且赋给同样的值，这样的话

2、随机指针 

3、next指针，并且把原来的链表去掉，只留下新的复制链表

class Solution {
public:
    Node* copyRandomList(Node* head)
   {
        /*1、复制每个节点，也就是在两个节点之间新建一个节点，复制前驱节点 */
        for(auto p = head; p;)//定义一个p，循环执行的条件是p存在
        {
            auto newp = new Node(p ->val);//创建一个节点，并且赋给val
            //在节点之间插入新节点
            auto temp = p ->next;//因为我们要在插入一个节点，后面的节点无法通过next指针访问了，只能保存         下一个节点的地址
            p ->next = newp;//指针指向新节点
            newp ->next = temp;
            p = temp;//p跳到下一个要插入的位置之前
        }
        /*2、开始设置复制节点的random指针*/
       for(auto p = head;p; p = p ->next->next)
       {
           if(p ->random)
           {
               p ->next->random = p ->random ->next;//random指针的指向
           }
       }
        /*3、从旧链表中分离出我们新生的复制链表，也就是指针只指向我们复制的新生节点*/
        Node* dummy = new Node(-1);//头节点
        Node* cur = dummy;
 
        for( auto p = head; p; p = p ->next)//p更新
        //p是旧链表的指针，cur是新链表的指针
        {
                  cur ->next = p ->next;//p->next就是我们复制生成的节点
                  cur = cur ->next;//cur更新
                  p ->next = p ->next ->next;//p指针执行下一个p
        }
       return dummy->next;
    }
};