反转链表
题目要求
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
解法：双指针法
思路
创建结点：temp，prev = NULL,cur = head
while使用cur遍历循环链表
temp指向头cur的下一个节点（保存cur的下一个结点）
cur的下一个节点指向prev（翻转操作）
更新prev,cur指针
如此循环，直到cur指向空指针(如下面图解)
最后返回prev
图解
代码
typedef struct ListNode LTNode; struct ListNode* reverseList(struct ListNode* head) { LTNode* temp; LTNode* prev = NULL; LTNode* cur = head; while(cur) { //保存cur的下一个结点 temp = cur->next; //翻转 cur->next = prev; //更新结点 prev = cur; cur = temp; } return prev; }
轮转数组
题目要求
给定一个整数数组
nums，将数组中的元素向右轮转k个位置，其中k是非负数。
示例
解法
方法一：数组方法
【时间复杂度O(n)】
方法二：memcpy法
【时间和空间复杂度O(n)】
代码
方法一
void Reverse(int* a,int left,int right) { while(left < right) { int tmp = a[left]; a[left] = a[right]; a[right] = tmp; ++left; --right; } } void rotate(int* nums, int numsSize, int k) { k %= numsSize; //前n-k个逆置 Reverse(nums,0,numsSize-k-1); //后k个逆置 Reverse(nums,numsSize-k,numsSize-1); //全部逆置 Reverse(nums,0,numsSize-1); }
方法二
void rotate(int* nums, int numsSize, int k) { k %= numsSize; int n = numsSize; int tmp[numsSize]; //前n-k个逆置 memcpy(tmp,nums+n-k,sizeof(int)*(k)); //后k个逆置 memcpy(tmp+k,nums,sizeof(int)*(n-k)); //全部逆置 memcpy(nums,tmp,sizeof(int)*(n)); }
