数组

双指针技巧1 同步指针

例题 反转字符串

编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1

输入:[“h”,“e”,“l”,“l”,“o”] 输出:[“o”,“l”,“l”,“e”,“h”]

示例 2

输入:[“H”,“a”,“n”,“n”,“a”,“h”] 输出:[“h”,“a”,“n”,“n”,“a”,“H”]

代码


class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0;
        int j = s.size() - 1;
        int temp = 0;
        while(s.size() > 0) {
            if(i == j || i - j == 1) {
                break;
            }
            temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
};

双指针技巧2 快慢指针

有时,我们可以使用两个不同步的指针来解决问题,即快慢指针。与情景一不同的是,两个指针的运动方向是相同的,而非相反。

例题 移除元素

给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

代码


class Solution {
 public:
     int removeElement(vector<int>& nums, int val) {
         int i = 0;  // 快指针
         int j = 0;  // 慢指针
         while(nums.size() > 0) {

             // 若该元素值不等于val
             if(nums[i] != val) {
                 if(i == nums.size()-1) {  // 若该元素为数组的末尾元素
                     nums[j] = nums[i];
                     return j+1;
                 }
                 nums[j] = nums[i];
                 i++;
                 j++;

             // 若该元素值等于val
             } else {
               if(i == nums.size()-1) {
                   return j;
               }
               i++;
             }
         }
         return 0;
     } 
 };

链表

你无法追溯单链表中的前一个结点。因此,您不仅要存储当前结点,还要存储前一个结点。

它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点:

(1)在调用 next 字段之前,始终检查节点是否为空。

获取空节点的下一个节点将导致空指针错误。例如,在我们运行 fast = fast.next.next 之前,需要检查 fast 和 fast.next 不为空。

(2)仔细定义循环的结束条件。

运行几个示例,以确保你的结束条件不会导致无限循环。在定义结束条件时,你必须考虑我们的第一点提示。

例题 删除链表的倒数第N个节点

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后,链表变为 1->2->3->5.

说明

给定的 n 保证是有效的。

进阶

你能尝试使用一趟扫描实现吗?

代码


/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }

        while(q){
            p = p->next;
            q = q->next;
        }

        ListNode* delNode = p->next;
        p->next = delNode->next;
        delete delNode;

        ListNode* retNode = dummyHead->next;
        delete dummyHead;

        return retNode;
    }
};