2019-02-18 leetcode

今日三道关于链表的题目（基础）：
1.合并两个有序链表：
合并链表是比较基础的题目了，主要就是几种情况：
--l1和l2有一个为空，则返回另一个。
--l1和l2均不为空，则挨个比较，每次连小的，并移动相应的指针。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1==nullptr){
            return l2;
        }
        if(l2==nullptr){
            return l1;
        }
        ListNode* res = nullptr;
        if(l1->val <= l2->val){
            res = l1;
            l1 = l1->next;
        }
        else{
            res = l2;
            l2 = l2->next;
        }
        ListNode* head = res;
        
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val <= l2->val){
                head->next = l1;
                head = head->next;
                l1 = l1->next;
            }
            else{
                head->next = l2;
                head = head->next;
                l2 = l2->next;
            }
        }

        head->next = l1 != nullptr ? l1: l2;
        return res;
    }
};

2.回文链表
回文链表的题目有进阶要求，显然我没达到。
我的想法就是，遍历链表，将其存在数组中，然后采用判断回文的方法进行判断。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int>s;
        while(head!=nullptr){
            s.push_back(head->val);
            head = head->next;
        }
        if(isPalindrome(s) == true){
            return true;
        }
        else{
            return false;
        }
    }
    bool isPalindrome(vector<int>s) {
        int len = s.size();
       
         for(int i=0, j=len-1; i<len/2,j>=i; ){         
            if(s[i] == s[j]){
                i++;
                j--;
                continue;
            }
            else{
                return false;
            }
        }
        return true;  
    }
};

3.环形链表
这个解法，快慢指针还是第一次看见。
参考博客：使用快慢指针的方法，设定两个指针，如果快指针追上慢指针则有环，如果指向了NULL则无环。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL)
        {
            return false;
        }
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast->next && fast->next->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                return true;
            }
        }
        return false;    
    }
};