链表

合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

递归

思路：首先判断是否存在空链表，若存在返回另一个即可。其次取两个链表的最小值相比较，将较大的节点拼接在较小的节点之后，保留较小的值，将剩余节点按照同样方法凭借，不断修改next的值即可。


class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr)
        {
            return list2;
        }else if(list2 == nullptr)
        {
            return list1;
        }else if(list1->val<list2->val){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }else {
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

迭代

思路：新建一条链表，设立哨兵节点，方便返回链表，每次取两条链表的最小值的节点，连接到新链表中，直到有链表为空，将剩余的存入新链表中，最后返回链表即可。


class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
      ListNode * temp=new ListNode(-1);
      ListNode * pre =temp;
      while(list1 !=nullptr &&list2 !=nullptr)
      {
          if(list1->val<list2->val)
          {
              pre->next=list1;
              list1=list1->next;
          }
          else{
               pre->next=list2;
              list2=list2->next;
          }
          pre=pre->next;
      }
      pre->next=list1==nullptr ?list2:list1;
      return temp->next;
    }
};

删除排序链表中的重复元素

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

思路：由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

具体地，我们从指针 cur指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next对应的元素相同，那么我们就将 cur.next从链表中移除；否则说明链表中已经不存在其它与 cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。

当遍历完整个链表之后，我们返回链表的头节点即可。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head)
        {
            return head;
        }
        ListNode* cur=head;
    while(cur->next)
    {
        if(cur->val==cur->next->val)
        {       
            cur->next=cur->next->next;
        }
        else{
            cur=cur->next;
        }
    }
    return head;
    }
};

环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

快慢指针法

我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode *slow=head;
        ListNode *fast=head->next;
        while(slow!=fast)
        {
            if(fast==nullptr||fast->next==nullptr  )
            {
                return false;
            }
            else{
                slow=slow->next;
                fast=fast->next->next;
            }
        }
        return true;
    }
};

哈希表法

我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> seen;
        while (head != nullptr) {
            if (seen.count(head)) {
                return true;
            }
            seen.insert(head);
            head = head->next;
        }
        return false;
    }
};

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

穷举暴力

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

哈希表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hashtable;
        for(int i =0; i<nums.size();++i)
        {
            auto it =hashtable.find(target-nums[i]);
            if(it!=hashtable.end()){
                return {it->second,i};
            }
            hashtable[nums[i]]=i;
        }
        return {};
    } 
};