876. Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

• The number of nodes in the given list will be between 1 and 100.

---

给定一个单向链表，要求找到其中间节点。

简单题，快慢指针，快指针的速度是慢指针的2倍，则当快指针走到末尾时，慢指针正好指向中间位置。代码如下：

class Solution {
public:
	ListNode* middleNode(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *fast = head, *slow = head;
		while (fast->next) {
			fast = fast->next->next;
			slow = slow->next;
			if (fast == NULL)break;
		}
		return slow;
	}
};

本代码提交AC，用时0MS。

143. Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

---

本题要求把单链表重新排序，规则是第一个节点接最后一个节点，第二个节点接倒数第二个节点，以此类推。要求in-place，不能借助额外的空间。 这个题我一开始想到的是递归解法，就是首先把L0和Ln接好，然后递归的在L1->…->L(n-1)重排序。但是这样的算法性能肯定很差，因为首先要找到尾节点就很麻烦，还要递归的找尾节点。

看了网上的题解，发现真是巧妙。把链表重排序之后的结果其实相当于先把链表从中点分成前后两段，然后把后半段链表逆序，最后合并两个链表，合并的时候交替从两个链表中取节点拼接起来。 举个例子，0->1->2->3->4，中点是2，分成两段之后就是0->1和2->3->4，然后把第二个链表逆序为4->3->2，最后交替拼接这两个链表，结果就是0->4->1->3->2。、 所以知道思路之后就好办了，找中点可以用快慢指针法，链表逆序用头插法，最后拼接也不是什么难事，不过整合起来代码稍微有点长。 完整代码如下：

class Solution {
public:
    void reorderList(ListNode* head)
    {
        if (head == NULL || head->next == NULL || head->next->next == NULL)
            return; // find mid node
        ListNode *slow = head, *fast = head, *pre = slow;
        while (slow->next != NULL && fast != NULL && fast->next != NULL) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = NULL;
        // reverse [mid,end]
        ListNode *par = new ListNode(0), *tail;
        while (slow) {
            tail = slow->next;
            slow->next = par->next;
            par->next = slow;
            slow = tail;
        }
        //merge 2 list
        par = par->next;
        ListNode *new_head = new ListNode(0), *h = new_head;
        while (head || par) {
            if (head == NULL) {
                h->next = par;
                par = par->next;
            }
            else {
                h->next = head;
                head = head->next;
                h = h->next;
                h->next = par;
                par = par->next;
            }
            h = h->next;
        }
        head = new_head->next;
    }
};

本代码提交AC，用时59MS。

LeetCode Odd Even Linked List Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity. Example: Given 1->2->3->4->5->NULL, return 1->3->5->2->4->NULL. Note: The relative order inside both the even and odd groups should remain as it was in the input. The first node is considered odd, the second node even and so on …

---

链表题，要求把链表中的奇数位节点连接起来，偶数位节点也连接起来，最后这两个链表连接起来。要求O(1)的空间复杂度和O(n)的时间复杂度。 因为奇数链表和偶数链表都是从原链表中隔一个取一个，立马联想到快慢指针，在这个题里，我们设置两个快指针fast1和fast2，分别指向奇数节点和偶数节点，然后分别取下来，接到odd和even链表中。最后把odd的tail指向even的head就搞定了。符合O(1)空间复杂度和O(n)时间复杂度。 完整代码如下： [cpp] class Solution { public: ListNode* oddEvenList(ListNode* head) { if (head == NULL)return head; ListNode *odd = new ListNode(0), *even = new ListNode(0); ListNode *otail = odd, *etail = even; ListNode *fast1 = head, *fast2 = head->next; while (fast1 || fast2) { otail->next = fast1; etail->next = fast2; if (otail)otail = otail->next; if (etail)etail = etail->next; if (fast2)fast1 = fast2->next; else fast1 = NULL; if (fast1)fast2 = fast1->next; else fast2 = NULL; } otail->next = even->next; return odd->next; } }; [/cpp] 本代码提交AC，用时16MS。 二刷。其实不用快慢指针，直接根据奇偶性就可以了，更简洁的代码如下： [cpp] class Solution { public: ListNode* oddEvenList(ListNode* head) { ListNode *odd = new ListNode(0), *even = new ListNode(0); int cnt = 1; ListNode *cur = head, *otail = odd, *etail = even; while(cur) { if(cnt & 1) { otail->next = cur; otail = otail->next; } else { etail->next =cur; etail = etail->next; } cur = cur->next; ++cnt; } otail->next = even->next; etail->next = NULL; // caution!!! return odd->next; } }; [/cpp] 本代码提交AC，用时19MS。]]>

287. Find the Duplicate Number 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n²).
4. There is only one duplicate number in the array, but it could be repeated more than once. 287. Find the Duplicate Number

---

一个长度为n+1的数组，包含1~n的数字，证明至少有一个数字重复，并找出这个重复数字。 证明好说，鸽巢原理。要求在线性时间复杂度和常数空间复杂度把这个重复的数字找出来就有难度了，而且不能修改原数组，难以用上LeetCode Find All Numbers Disappeared in an Array的技巧。 这题确实hard，看了看提示，以及网上的题解，现总结如下。 第一种解法是二分搜索。根据鸽巢原理，如果有n+1个[1,n]的数，则必有一个数重复了，把区间分成[1,m]和[m+1,n]，则重复的数字要么出现在[1,m]，要么出现在[m+1,n]，所以只需统计一下小于等于和大于m的数字的个数，数字多的那个区间肯定是存在重复数字的区间。然后在那个区间递归的找下去，直到找到重复数字。
完整代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int low = 1, high = nums.size() – 1;
        while (low < high) {
            int mid = (low + high) / 2, low_cnt = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i] <= mid)
                    ++low_cnt;
            }
            if (low_cnt > mid) {
                high = mid;
            }
            else {
                low = mid + 1;
            }
        }
        return low;
    }
};

本代码提交AC，用时9MS。
还有一种解法和LeetCode Linked List Cycle II很类似，如果存在重复数字，则使用下标递归访问的时候，会出现循环访问。首先通过快慢指针找到循环相遇点，然后慢指针回到原点，快慢指针按相同速度前进，直到遇到函数值相同时停止，这个相同的函数值即为重复数字。一些证明可以参考这个博客。
完整代码如下：

class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast)
                break;
        }
        slow = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[fast];
            if (slow == fast)
                return slow;
        }
    }
};

本代码提交AC，用时13MS。

二刷。对二分搜索的解读。假设数组没有重复数字，比如[1,2,3,4,5,6,7]，则对于任意一个数x，<=x的数的个数和x是相等的，比如<=1的数有1个，<=2的数有2个etc…如果出现重复数字，假设比中点小，则<=m的数的个数要大于m。所以代码中每次比较是low_cnt和m比较。

l、r、while(l<=r)都是标准的二分搜索框架。最后返回r+1，想象一直low_cnt>m，知道不满足while循环，则最后一个满足的就是r+1。

class Solution {
public:
	int findDuplicate(vector<int>& nums) {
		int n = nums.size();
		int l = 1, r = n - 1;
		while (l <= r) {
			int m = l + (r - l) / 2;
			int low_cnt = 0;
			for (int i = 0; i < n; ++i) {
				if (nums[i] <= m)++low_cnt;
			}
			if (low_cnt > m)r = m - 1;
			else l = m + 1;
		}
		return r + 1;
	}
};

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:
Can you solve it without using extra space?

---

本题在LeetCode Linked List Cycle的基础上更进一步，需要求出链表中环的起点位置。 接上一题，相遇位置在Z，此时如果令slower=head，然后slower和faster都以相同的速度走a步，则slower刚好能到环的起点位置Y，那么faster会在哪里呢。 上一题推出来相遇的时候有：a+b=(n-2m)c，如果faster在相遇点走a步，则相当于走了a=(n-2m)c-b，(n-2m)c相当于绕圈n-2m次，(n-2m)c-b的意思就是在z点绕圈n-2m次的基础上，退回b步，看图，退回b步正好到达了环的起点Y。 所以快慢指针再走a步之后，正好在环的起点相遇了！ 于是本题的思路就是：先用上一题的方法找到相遇位置，然后slower回到head节点，slower和faster都再次单步走，再次相遇时，就是环的起点。 完整代码如下：

class Solution {
public:
    ListNode* detectCycle(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
            if (faster == slower)
                break;
        }
        if (faster->next == NULL || faster->next->next == NULL)
            return NULL;
        slower = head;
        while (slower != faster) {
            slower = slower->next;
            faster = faster->next;
        }
        return slower;
    }
};

本代码提交AC，用时13MS。

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

---

本题要判断一个链表中是否包含环，注意这里的环可能是局部的环，并不一定是链表头尾相连那种环，比如下图。 解题思路是使用快慢指针，如果链表中有环，则快慢指针一定会在某处相遇，证明请看这篇博客，我试着重述一遍： 首先请看示意图，假设链表起点为X，环的起点为Y，环的总长度为c，快慢指针在环的Z点相遇，YZ=b，XY=a。则有

a+b+mc=s—(1)

a+b+nc=2s—-(2)

(1)和(2)式分别为慢快指针的等式，其中s表示慢指针走过的节点，则快指针走过两倍的s，m和n分别为慢快指针绕圈的圈数，显然n>m。 把(1)代入(2)得到a+b=(n-2m)c。假设真的存在环，则a和c是链表的固有值，是已知量，所以如果能找到m,n,b的一组解，则说明假设成立，真的存在环。 令m=0,n=a,b=ac-a，则这一组解是满足上面的方程(1)和(2)的，也满足n>m。因为环的长度>1，所以b也是大于0的。既然找到一组解，说明假设成立，即存在环。也就是说，我们可以用这种方法判断环是否存在。 完整代码如下：

class Solution {
public:
    bool hasCycle(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return false;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
            if (faster == slower)
                return true;
        }
        return false;
    }
};

本代码提交AC，用时9MS。
证明参考：
https://stackoverflow.com/a/6110767/2468587
https://math.stackexchange.com/a/913529/161019

234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space? 234. Palindrome Linked List

---

本题要判断一个单向链表是否为回文链表。之前LeetCode Valid Palindrome判断的是数组，可以直接访问数组的头尾元素，但是链表不可以随机访问。 仔细观察一下，下面两条回文链表：

1. 1->2->3->4->5->4->3->2->1
2. 1->2->3->4->4->3->2->1

判断回文链表最原始的方法是从左往右读一遍和从右往左读一遍，如果读得的结果一样就是回文，比如第1条回文，从左往右是123454321，从右往左也是123454321，所以它是回文。 但是其实我们可以不用完整读一遍，我们只读一半就可以了，比如回文1的前半部分是1234，后半部分是4321，前半部分顺着读和后半部分倒着读都是1234，这样就足以说明是回文串了。 紧接着，对于链表，我们就有这样一种解题思路：首先找到链表的中间节点，然后把后半部分链表逆序，最后看看逆序的后半部分和顺序的前半部分是否相同。 找链表的中间节点的常规思路就是快慢指针，这个在很多题中都用到了，需要指出的是，回文链表有两种情况，一种是形如1的奇数个元素，另一种是形如2的偶数个元素。如果用快慢指针找中点，1能找到真正的中点5，2能找到前一个中点4，所以我们判断回文的时候，只需要把中点后面的链表逆序，然后只比较后半部分的链表元素。比如1的情况，逆序后半部分之后得到1->2->3->4，那么前半部分也只需要比较1->2->3->4，不需要比较5，因为这是奇数链表的中点，前后链表共享的元素；2的情况，逆序后半部分之后得到1->2->3->4，前半部分也是1->2->3->4，偶数长度的情况就会把中间的两个元素分到前后两部分。 完整代码如下：

class Solution {
public:
    bool isPalindrome(ListNode* head)
    {
        if (head == NULL || head->next == NULL)
            return true;
        ListNode *faster = head, *slower = head;
        while (faster->next != NULL && faster->next->next != NULL) {
            faster = faster->next->next;
            slower = slower->next;
        } //bool odd = faster->next == NULL ? true : false; // 链表长度是否为奇数
        ListNode *head2 = slower, *prior = slower->next, *tail;
        head2->next = NULL;
        while (prior != NULL) { // 逆序后半段链表
            tail = prior->next;
            prior->next = head2->next;
            head2->next = prior;
            prior = tail;
        }
        head2 = head2->next;
        while (head2 != NULL) {
            if (head->val != head2->val)
                return false;
            head = head->next;
            head2 = head2->next;
        }
        return true;
    }
};

本代码提交AC，用时25MS。

二刷。同样的思路：

class Solution {
public:
	bool isPalindrome(ListNode* head) {
		if (head == NULL || head->next == NULL)return true;
		// 快慢指针
		ListNode *fast = head, *slow = head;
		while (fast != NULL && fast->next != NULL) {
			fast = fast->next->next;
			slow = slow->next;
		}
		// 逆序后半段
		ListNode *dummy = new ListNode(0);
		ListNode *par = slow, *child = slow->next;
		while (par != NULL) {
			child = par->next;
			par->next = dummy->next;
			dummy->next = par;
			par = child;
		}
		// 判断是否相等
		slow = head;
		fast = dummy->next;
		while (fast != NULL) {
			if (slow->val != fast->val)return false;
			slow = slow->next;
			fast = fast->next;
		}
		return true;
	}
};

本代码提交AC，用时28MS。

109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

---

这一题和之前的LeetCode Convert Sorted Array to Binary Search Tree思路是一样的，只是把数组换成了链表，这样的话，就不能通过下标直接访问到中点元素了。 此时只能通过遍历找到链表的中点，然后以中点为根节点建树，最后分割左右链表，递归建树。完整代码如下：

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head)
    {
        if (head == NULL)
            return NULL;
        if (head->next == NULL)
            return new TreeNode(head->val);
        int n = 0, cnt = 0;
        ListNode* tmp = head;
        while (tmp != NULL) {
            n++;
            tmp = tmp->next;
        }
        tmp = head;
        while (cnt < n / 2 – 1) {
            tmp = tmp->next;
            cnt++;
        } // 此时tmp是中间节点的上一个节点
        TreeNode* root = new TreeNode(tmp->next->val);
        ListNode* head2 = tmp->next->next;
        tmp->next = NULL; // 断开
        root->left = sortedListToBST(head);
        root->right = sortedListToBST(head2);
        return root;
    }
};

本代码提交AC，用时22MS。击败了87%的人:-)
后来想想这题会不会有更优的解法，网上看了一下，发现自己蠢到哭了，链表找中点居然用了这么笨的方法，之前的快慢指针都忘了。换上快慢指针找链表中点的解法如下：

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head)
    {
        if (head == NULL)
            return NULL;
        if (head->next == NULL)
            return new TreeNode(head->val);
        ListNode *fast = head, *slow = head, *prior = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            prior = slow;
            slow = slow->next;
            fast = fast->next->next;
        } // 此时slow为中间节点，prior为中间节点的上一个节点
        TreeNode* root = new TreeNode(slow->val);
        ListNode* head2 = slow->next;
        prior->next = NULL; //断开
        if (head != slow)
            root->left = sortedListToBST(head);
        root->right = sortedListToBST(head2);
        return root;
    }
};

本代码提交AC，用时26MS，有点失望，按理说这种解法是要比我上面的解法快的。
后来我又发现，这两种解法构建出来的平衡二叉搜索树不一样，如下图所示，但是他们都还算紧凑，都是正确的，看来答案不唯一啊。（其实主要是偶数长度时，有两个中间节点，选哪个都是正确的。）

61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

---

这一题要把链表的后k个右旋到开头，其实就是把后k个节点断开，然后接到开头。思路是先遍历一遍得到链表长度n，然后k=k%n。再从头开始找第n-k-1个，断开然后拼接到开头即可。 完整代码如下：

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k)
    {
        if (head == NULL || head->next == NULL || k == 0)
            return head;
        int n = 1, cut_pos = 0;
        ListNode* tail = head;
        while (tail->next != NULL) {
            n++;
            tail = tail->next;
        }
        //while (k >= n)k -= n;
        k = k % n;
        if (k == 0)
            return head;
        ListNode* new_tail = head;
        while (cut_pos + k + 1 < n) {
            new_tail = new_tail->next;
            cut_pos++;
        }
        ListNode* new_head = new_tail->next;
        new_tail->next = NULL;
        tail->next = head;
        return new_head;
    }
};

本代码提交AC，用时20MS。

还可以其他一些思路，比如把连接头尾相连成一个环，然后找到断开的位置；或者使用快慢指针找到需要断开的位置，快指针先走k步，慢指针再从头开始走，当快指针到末尾时，慢指针就到断开位置了。其实吧，我觉得直接找第n-k-1的位置，应该不比快慢指针慢吧，不知道为什么我这个花了20MS。

二刷。思路跟之前的一样，代码更好看一点。

class Solution {
public:
	int GetListLength(ListNode* head) {
		int len = 0;
		while (head) {
			++len;
			head = head->next;
		}
		return len;
	}
	ListNode* rotateRight(ListNode* head, int k) {
		int len = GetListLength(head);
		if (len == 0 || len == 1)return head;
		k = k % len;
		if (k == 0)return head;
		int l = len - k;
		ListNode *first = head;
		while (--l) { // 注意是--l，不是l--，停在断开前一个位置
			first = first->next;
		}
		ListNode *second = first->next;
		first->next = NULL;
		first = second;
		while (first->next)first = first->next;
		first->next = head;
		return second;
	}
};

本代码提交AC，用时8MS。

27. Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

---

要求我们把数组中等于某个数的元素全部“移除”，移除并不是真正的移除，可以把它们移到数组的末尾。

我的思路是，i指针从前往后扫，遇到一个等于val的（需要移除的）元素时，j从i+1开始找一个不等于val的，交换i,j指向的元素，i继续前进。
思路还是很简单，结果也正确，但是在计算新数组的长度时需要考虑较多cases，太麻烦，我就直接从末尾再往前找，直到找到一个不等于val的下标位置。ugly代码：

class Solution {
public:
    int removeElement(vector<int>& nums, int val)
    {
        if (nums.size() == 0)
            return 0;
        if (nums.size() == 1)
            return (nums[0] != val) ? 1 : 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < nums.size(); j++) {
                    if (nums[j] != val) {
                        nums[i] = nums[j];
                        nums[j] = val;
                        break;
                    }
                }
            }
        }
        if (nums[0] == val)
            return 0;
        else {
            int i;
            for (i = nums.size() – 1; i >= 0; i–)
                if (nums[i] != val)
                    break;
            return i + 1;
        }
    }
};

本代码提交AC，用时4MS，排名倒数也是在我的预料之中的。看过题解之后，不得不感慨自己还是太笨，过段时间再来刷一遍。

二刷。这题其实很简单，也相当于快慢指针，快指针j一直走，如果nums[j]!=val，则把nums[j]赋值给nums[i]，同时i也往前走；如果nums[j]==val，则i要停下来，相当于i这个位置指示了可以放合法元素的位置。完整代码如下：

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

本代码很简洁，提交AC，用时4MS。