第六章 双指针

1. 删除链表的节点

数据结构最简单的操作之一。但是居然耗了好久，关于链表的基本功不够！

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head->next;
        ListNode *pre = head, *cur = head->next;
        while(cur != nullptr && cur->val != val) {
            pre = cur;
            cur = cur->next;
        }
        if(cur != nullptr) pre->next = cur->next;
        return head;
    }
};

2. 调整数组顺序使奇数位于偶数前面

和双指针无关，最简单的想法，创建一个vector，奇数头插，偶数尾插。但是效率极低。

class Solution {
private:
    vector<int> res;
public:
    vector<int> exchange(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i]%2==0)
                res.push_back(nums[i]);
            else
                res.insert(res.begin(),nums[i]);
        }
        return res;
    }
};

执行用时：1384 ms, 在所有 C++ 提交中击败了5.35%的用户
内存消耗：19.2 MB, 在所有 C++ 提交中击败了5.04%的用户

用双指针试试：
设置两个指针，分别从左右两边开始找，左边找到第一个偶数，右边找到第一个奇数，然后交换一下。继续走直到双方碰面。

class Solution {
public:
    vector<int> exchange(vector<int> &nums) {
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            while (nums[i] % 2 != 0 && i < j)
                i++;
            while (nums[j] % 2 == 0 && i < j)
                j--;
            swap(nums[i], nums[j]);
        }
        return nums;
    }
};

3. 链表中倒数第 k 个节点

自己第一遍想的是先遍历一遍，然后统计出个数，然后n-k就能找到第k个节点之后的链表。但是时间复杂度太高了，根本没有用出来双指针，再思考发现用第一个指针往前走k，然后和第二个指针同步往前走，刚好第二个指针就是答案所要的头节点。

class Solution {
public:
    ListNode *getKthFromEnd(ListNode *head, int k) {
        if (head== nullptr)
            return nullptr;
        ListNode* curr = head;
        ListNode* per = head;
        for (int i = 1; i < k; ++i) {
            curr=curr->next;
        }
        while (curr->next!= nullptr){
            curr=curr->next;
            per=per->next;
        }
        return per;
    }
};

4. 合并两个排序的链表、

自己想法是插入，以l1为基础，设置两个指针，将l2中的节点插入l1中，用了一晚上，没做出来，各种出错。先是答案错误，后面出现了空指针的问题。一晚上也没debug出来。后面看了解析，通过新建一个头节点，两个指针分别在l1和l2中进行遍历，依次加到新的头节点后。

class Solution1 {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *curr = l1;
        if (l1 == nullptr)
            return l2;
        ListNode *next = l1->next;
        ListNode *p2 = l2;
        if (l2 == nullptr)
            return l1;
        while (curr != nullptr) {
            if (curr->val <= p2->val) {
                ListNode *node = new ListNode;
                node->val = p2->val;
                node->next = next;
                curr->next = node;
                p2 = p2->next;
            }
            if (curr->val > p2->val) {
                ListNode *node = new ListNode;
                node->val = p2->val;
                node->next = curr;
                curr = node;
            }
            curr = next;
            if (next == nullptr) {
                break;
            }
            next = next->next;
            if (p2 == nullptr)
                break;
        }
        if (p2 != nullptr)
            curr->next = p2;
        return l1;
    }
};
class Solution2 {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *per = l1;
        ListNode *curr = l1;
        ListNode *p2 = l2;
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        while (curr != nullptr) {
            if (curr->val >= p2->val) {
                ListNode *node = new ListNode;
                node->val = p2->val;
                node->next = curr;
                per->next = node;
                p2 = p2->next;
            }
            per = curr;
            curr = curr->next;
        }
        if (p2 != nullptr) {
            curr->next = p2;
        }
        return l1;
    }
};
//正确答案
class Solution3 {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *res = new ListNode(0);
        ListNode *cur = res;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = l1 != nullptr ? l1 : l2;
        return res->next;
    }
};

5. 翻转单词顺序

先去除最前面的空格，然后反转每一个单词(通过空格来控制)，最后整体反转。

class Solution {
public:
    string reverseWords(string s) {
        string ans;
        int i = 0;
        while (i < s.size()) {
            //去掉空格
            while (i < s.size() && s[i] == ' ') i++;
            int j = i;
            //取单词
            while (j < s.size() && s[j] != ' ') j++;
            if (j > i) {
                string sub = s.substr(i, j - i);
                reverse(sub.begin(), sub.end());
                if (ans.size()) ans += ' ';
                ans += sub;
            }
            i = j;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
class Solution1 {
public:
    string reverseWords(string s) {
        int i = 0;
        string res;
        while (i < s.size()) {
            //去空格
            while (i < s.size() && s[i] == ' ')
                i++;
            //取单词
            int j = i;
            while (j < s.size() && s[j] != ' ')
                j++;
            //反转单词
            if (j > i) {
                string sub = s.substr(i, j - i);
                reverse(sub.begin(), sub.end());
                if (res.size()) 
                    res += ' ';
                res += sub;
            }
            i = j;
        }
        //整体反转
        reverse(res.begin(), res.end());
        return res;
    }
};

在去空格和取单词的时候，没加限定i和j都要< s.size()；导致溢出。之后在res中单词直接加入空格的时候又出错，发现需要再加一个if来判断。