数据结构笔记4：数组、链表OJ
目录
数组OJ题：
轮转数组：
消失的数字：
链表OJ题：
返回倒数第k个节点：
链表的回文结构：
相交链表：
随机链表的复制（链表的深拷贝）
数组OJ题：
轮转数组：
void reverse(int *nums,int left,int right)
{while(left<right){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k) {k %= numsSize;reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-k-1);reverse(nums,0,numsSize-1);/*reverse(nums,0,numsSize-1);reverse(nums,0,k-1);reverse(nums,k,numsSize-1);*/
}对于这道题目，可以采用逆置数组的方式来实现，首先写一个局部轮转的函数，然后再进行三段逆置。（可以先逆置整体再逆置前（k%numsSize）个数字）（也可以先逆置后(k%numsSize）个数字再逆置整体），达到数组轮转的效果。
消失的数字：
一种方法是牺牲空间复杂度来换取时间复杂度。创建一个临时数组，在下标为nums[i]的位置将值置为1。
int* tmp = calloc(numsSize+1,sizeof(int));for(int i = 0;i<numsSize;i++){tmp[(nums[i])] += 1;}int ret = 0;for(int i = 0;i<numsSize+1;i++){if(tmp[i] == 0){ret = i;}}return ret;第二种方法则更加巧妙：利用异或的性质（相同数字异或为0,0和任何数异或都为其本身），先异或从0到n的所有数字，再异或数组的所有数字，剩下的就是消失的数字。
int ret = 0;for(int i = 0;i <= numsSize;i++){ret ^= i;}for(int i = 0;i < numsSize;i++){ret ^= nums[i];}return ret;链表OJ题：
返回倒数第k个节点：
方法一：先找出链表节点个数，再返回倒数第k个节点。
struct ListNode* cur = head;int size = 0;while(cur){size++;cur = cur->next;}cur = head;for(int i = 1;i < (size-k+1);i++){cur = cur->next;}return cur->val;方法二：快慢指针法，快指针先走k步，慢指针再和快指针一起走，返回慢指针的值。
struct ListNode* fast = head;struct ListNode* slow = head;while(k--){fast = fast->next;}while(fast){fast = fast->next;slow = slow->next;}return slow->val;链表的回文结构：
链表的回文结构是指一个链表从前往后读和从后往前读的顺序是一样的。换句话说，链表中的元素序列是对称的。
使用反转链表后半部分的方法（因为单链表只能从前向后遍历），然后分别从链表的后半部分和前半部分开始遍历：
class PalindromeList {
public:ListNode* middleNode(ListNode *head){ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}return slow;}ListNode* reverseList(ListNode* head){ListNode* cur = head;ListNode* prev = NULL;while(cur){ListNode* next = cur->next;cur->next = prev;prev = cur;cur = next;}return prev;}bool chkPalindrome(ListNode* A) {//回文结构就是从前往后和从后往前读都是一样的//从中间节点开始逆序链表//从前往后读，从后往前读比较值是否一样ListNode * mid = middleNode(A);ListNode * change = reverseList(mid);ListNode* cur = A;while(change){if(change->val != cur->val)return false;cur = cur->next;change = change->next;}return true;}
};相交链表：
首先判断两个链表是否相交，相交链表的最后一个节点一定相等，不相交链表的最后一个节点一定不等。
然后让长度更长的链表先走abs（len1-len2）步。再遍历两个链表判断是否相等。
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {ListNode* cur1 = headA;ListNode* cur2 = headB;int len1 = 1;int len2 = 1;//先判断是否香蕉//香蕉的链表最后一个节点是一样的while(cur1->next){len1++;cur1 = cur1->next;}while(cur2->next){len2++;cur2 = cur2->next;}if(cur1 != cur2){return NULL;}int gap = abs(len1-len2);//假设法ListNode * longlist = headA;ListNode * shortlist = headB;if(len1 < len2){longlist = headB;shortlist = headA;}//长链表先走while(gap--){longlist = longlist->next;}while(longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}return longlist;
}随机链表的复制（链表的深拷贝）
这道题最困难的地方就是对于随机值的拷贝。
如果只是链表的拷贝的话，可以采用遍历链表的方式通过创建新节点来实现拷贝。但是却没办法实现原来对随机值的拷贝。
并且题目要求的随机值（random）并不是说指向的节点值一样就可以了，而是要保持和原链表一模一样的结构。
为了实现这种深拷贝，先在原链表的每个节点后面创建一个值和原来节点一样的节点（就形成了一种原来节点下一个节点是拷贝节点的结构），然后再遍历这些新节点，让它们的random值指向原来节点的random值的下一个节点
这样就实现了对随机值的拷贝，然后再将这些复制的节点从原链表中剪下来。
新的拷贝链表就完成了。
typedef struct Node Node;
Node * BuyNode(int x)
{Node* node = (Node*)malloc(sizeof(Node));node->val = x;return node;
}
struct Node* copyRandomList(struct Node* head) {
//先将新节点插到旧节点前面if(head == NULL)return head;Node* cur = head;while(cur){Node* next = cur->next;Node* newnode = BuyNode(cur->val);newnode->next = cur->next;cur->next = newnode;cur = next;}cur = head;
//对随机值的拷贝while(cur){if(cur->random == NULL){cur->next->random = NULL;}else{cur->next->random = cur->random->next;}cur = cur->next->next;}//把拷贝的链表剪下来cur = head;Node* newhead = cur->next;Node* cur2 = newhead;while(cur){cur2 = cur->next;cur->next = cur2->next;cur = cur->next;if(cur != NULL)cur2->next = cur->next;}cur2->next = NULL;return newhead;
}