86. Partition List
题目
分析：题目要求将链表划分为两部分，前半部分小于x，后半部分大于等于x，并且各个数之间的相对顺序不变。
解题思路是：从头开始扫描链表，找打第一个大于等于x的数current，然后从这个数开始，把current之后的小于x的数依次插在current前，大于等于x的数不变；为了实现插入操作，可以新建一个带头节点的链表。
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if(NULL == head)
return NULL; ListNode *pHead = new ListNode();//新创建一个链表
ListNode *pre = pHead;//添加一个头节点 ListNode *current = head;
while(current != NULL)//找到第一个大于等于x的节点
{
if(current->val <x)
{
pre->next = new ListNode(current->val);//小于x的节点，原封不动的copy到新链表中
pre = pre->next;
}
else
break;
current = current->next; }
ListNode *temp = current; while(temp!=NULL)//处理current之后小于x的节点
{
if(temp->val <x)
{
pre->next = new ListNode(temp->val);
pre = pre->next;
}
temp = temp->next;
}
temp = current;
while(temp!=NULL)//处理current之后大于等于x的节点
{
if(temp->val >=x)
{
pre->next = new ListNode(temp->val);
pre = pre->next;
}
temp = temp->next;
} return pHead->next; }
};
----------------------------------------------------------------------分割线----------------------------------------------------------------------------
88. Merge Sorted Array
题目
分析：注意题目的空间复杂度的要求
代码：
class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int i,j;
int index = m+n-;
if ( == n)
{
return ;
}
if ( == m && != n)
{
for (i=;i<n;i++)
{
A[i]=B[i];
}
return ;
}
for(i=m-,j=n-;index>=;)
{
if (A[i]>B[j])
{
A[index]=A[i];
i--;
}
else
{
A[index]=B[j];
j--;
}
index--;
if (j<||i<)
{
break;
}
}
if (i<)
{
for (i=j;i>=;i--)
{
A[index]=B[i];
index--;
}
}
}
};-----------------------------------------------------------------------分割线------------------------------------------------------------
89. Gray Code
题目
分析：主要理解格雷码的镜像构造法
代码
class Solution {
public:
vector<int> grayCode(int n) {
//if(n<=)
vector<int> res;
res.push_back();
int count=;
int index;
int temp;
unsigned int x;
while(count<=n)
{
x = ( << (count-));
index = res.size()-;
while(index>=)
{
temp = res[index];
temp = temp|x;
res.push_back(temp);
index--;
}
count++;
}
return res;
}
};