数据结构——顺序表单链表oj详解

之前我们讲解了顺序表和单链表这两个数据结构，但是仅仅掌握它们的实现方法是远远不够的，我们还需要通过刷算法题对已有知识进行巩固和利用。

27. 移除元素 - 力扣（LeetCode）

思路一：这一题我们可以想到一种十分简单的思路：再创建一个同等大小数组arr，从0开始遍历原来的数组nums，如果当前被遍历到的元素的值不等于val，那就将这个值放到arr数组中，遍历完以后，arr数组中的元素个数就是原来数组中值不为val的元素个数，再将这些元素放到nums数组中

代码：

int removeElement(int* nums, int numsSize, int val)
{if (numsSize == 0){return 0;}//思路一：创建一个新的数组arr，将nums数组中值不为val的元素放到arr中int arr[numsSize];int k = 0;for (int i = 0; i < numsSize; i++){if (nums[i] != val){arr[k++] = nums[i];}}for (int i = 0; i < k; i++){nums[i] = arr[i];}return k;
}

这个算法的时间复杂度是O(N)，空间复杂度也是O(N)。

有没有什么方法使得空间复杂度降为O(1)呢？

有的兄弟们有的。

思路二：那就是双指针法：我们定义两个“指针”a和b，初始时两个指针都指向数组的起始位置，然后让其中一个指针b往前探路，如果b指向的元素不为val，就让a所指向的位置的值等于b所指向的位置的值，然后再让a和b同时往前走，如果b所指向的元素等于val，就让b往前走，a不动。最终a之前的元素个数就是数组中值不为val的元素个数

代码：

int removeElement(int* nums, int numsSize, int val)
{//思路二，双指针法int a = 0, b = 0;while (b < numsSize){if (nums[b] != val){nums[a] = nums[b];a++;}b++;}return a;
}

26. 删除有序数组中的重复项 - 力扣（LeetCode）

思路一：创建一个新的数组arr，将arr的第一个元素设为nums[0],不断遍历原数组，如果遍历到的元素与arr数组中最后一个元素不同，就将这个元素的值放到arr数组中当前最后一个元素的下一个位置。

代码：

int removeDuplicates(int* nums, int numsSize)
{//创建新的数组if (numsSize == 0){return 0;}int arr[numsSize];int a = 1, b = 0;arr[0] = nums[0];while (a < numsSize){if (nums[a] != arr[b]){arr[++b] = nums[a];}a++;}for (int i = 0; i <= b; i++){nums[i] = arr[i];}return b + 1;
}

上面的代码定义了两个变量，分别指向了两个数组。

上面代码的时间复杂度为O(N)，空间复杂度O(N）。

其实，这个思路也可以用另一种写法，不用创建一个新的数组，而是直接在原数组的基础上进行改动。这种方法跟上一题的第二种思路相似，也是双指针法：

//双指针法
int removeDuplicates(int* nums, int numsSize)
{int b = 0, a = 1;while (a < numsSize){if (nums[a] != nums[b] && b != a){nums[++b] = nums[a];}a++;}return b + 1;
}

• 88. 合并两个有序数组 - 力扣（LeetCode）

思路：我们知道的是nums1这个数组的空间大于nums2这个数组的空间，并且nums1中多余的空间（没有存放有效元素的空间）在nums1的后面，所以在考虑合并两个数组的元素时，我们可以考虑先从nums1中后面的元素填充值，我们已知两个数组原来是按照非递减序列排列的，并且要求合并后的数组也是按照非递减序列排列，这样的话，我们就要考虑优先将元素值较大的元素往后放，也就是要从两个数组的最后一个有效数据开始比较元素大小，从后往前存放元素，基于此，我们可以写出代码：

//从后往前，由大到小开始插入
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int a = m - 1, b = n - 1, c = m + n - 1;while (a >= 0 && b >= 0){if (nums1[a] >= nums2[b]){nums1[c] = nums1[a--];}else{nums1[c] = nums2[b--];}c--;}while (b >= 0){nums1[c--] = nums2[b--];}
}

• 203. 移除链表元素 - 力扣（LeetCode）

思路：我们可以创建一个新的链表，注意哦，此处创建新的链表并不是重新去创建每个节点，然后将遍历原链表然后获取新链表中每个节点的值。我们是要根据原有的节点创建新链表，新链表中的节点就是原来的链表的节点，遍历原链表，将值不为val的节点尾插至新链表。

代码：

typedef struct ListNode ltnode;
struct ListNode* removeElements(struct ListNode* head, int val)
{//如果原链表为空，直接返回if (head == NULL){return head;}ltnode* newhead = NULL;ltnode* newtail = NULL;ltnode* pcur = head;while (pcur){if (pcur->val != val){//尾插if (newhead == NULL){newhead = newtail = pcur;}else{newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}//需要先检查新链表是否为空再让newtail的下一个节点为空if (newhead)newtail->next = NULL;return newhead;
}

其实上面的代码还可以在进行优化，我们可以像双链表那样为新链表设置一个哨兵位节点（即带头节点），这样就可以直接将节点尾插到新链表中了：

typedef struct ListNode ltnode;
struct ListNode* removeElements(struct ListNode* head, int val)
{ltnode* newhead = (ltnode*)malloc(sizeof(ltnode));newhead->next = NULL;ltnode* newtail = newhead;ltnode* pcur = head;while (pcur){if (pcur->val != val){newtail->next = pcur;newtail = newtail->next;}pcur = pcur->next;}newtail->next = NULL;return newhead->next;}

可以看到，优化后的代码相较于上一个代码简洁了许多。

• 206. 反转链表 - 力扣（LeetCode）

这道题的思路就比较新奇了，我们先直接来看代码，结合图解来理解这道题的做法：

 typedef struct ListNode ltnode;
struct ListNode* reverseList(struct ListNode* head) 
{if(head==NULL){return NULL;}ltnode*p1=NULL,*p2=head,*p3=head->next;while(p2){p2->next=p1;p1=p2;p2=p3;if(p3)p3=p3->next;}return p1;
}

• 876. 链表的中间结点 - 力扣（LeetCode）

思路1：计数法，遍历整个链表，记录链表的长度，然后再循环找到中间位置

typedef struct ListNode ltnode;
struct ListNode* middleNode(struct ListNode* head)
{//思路一：计数法，先遍历链表统计链表的总长度，然后再据此遍历链表找到链表的中间节点int len = 0;ltnode* pcur = head;while (pcur){len++;pcur = pcur->next;}len = len / 2;pcur = head;while (len--){pcur = pcur->next;}return pcur;
}

思路2：快慢指针：慢指针每次走一步，快指针每次走两步，当快指针走到尽头时，慢指针恰好走到中间位置,这就好像初中学到的物理中的位移与时间的问题，当slow和fast的时间相同，他们的位移量就决定于自己的速度，所以当fast走到尽头的时候，slow的位移量刚好是fast的一半：

 typedef struct ListNode ltnode;
struct ListNode* middleNode(struct ListNode* head) 
{ltnode*slow=head,*fast=head;while(fast&&fast->next)//注意顺序：不能倒过来哦，如果倒过来，就会发生空指针解引用的问题
//而由于短路原理，此处当fast为空的时候，就会直接跳出循环，不会导致空指针解引用的问题{slow=slow->next;fast=fast->next->next;}return slow;
}

• 21. 合并两个有序链表 - 力扣（LeetCode）

这道题也可以创建一个带有空头结点的新链表，然后遍历原来的两个链表，比较后将节点插入到新的链表：

typedef struct ListNode ltnode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1==NULL){return list2;}if(list2==NULL){return list1;}ltnode*head=(ltnode*)malloc(sizeof(ltnode));ltnode*tail=head;head->next=NULL;while(list1&&list2){if(list1->val<=list2->val){tail->next=list1;tail=tail->next;list1=list1->next;}else{tail->next=list2;tail=tail->next;list2=list2->next;}}if(list1){tail->next=list1;}if(list2){tail->next=list2;}ltnode*newnode=head->next;free(head);
return newnode;
}

• 链表的回文结构_牛客题霸_牛客网

联系到这里，才真的算开始游戏。这一道题是比较有挑战性的一道题，但是有了我们前面那些题目的铺垫，这道题的解题步骤就比较简单了，主要这个思路应该该怎么想捏？

比如题目给的样例：1->2->2->1,他是一个回文数组，因为从中间开始往后如果我们将链表翻转过来，那么反转后的部分就变成了：1->2，此时翻转后的部分与从开头到中间部分的内容对应相等。

这就为我们提供了思路：我们可以先找到中间位置，然后从中间位置向后开始反转链表，如果反转之后的链表与从开头位置到中间的节点值对应相等，那就说明这是一个回文结构的链表，而我们之前又凑巧写了寻找中间节点和翻转链表的代码，正好可以CV（复制粘贴）到这里，简直是天助我也。思路有了，就来上手写代码吧：

typedef struct ListNode ltnode;
//寻找中间节点：struct ListNode* middleNode(struct ListNode* head) {ltnode* slow = head, *fast = head;while (fast &&fast->next) //注意顺序：不能倒过来哦，如果倒过来，就会发生空指针解引用的问题
//而由于短路原理，此处当fast为空的时候，就会直接跳出循环，不会导致空指针解引用的问题{slow = slow->next;fast = fast->next->next;}return slow;}
//从中间节点开始向后反转链表：struct ListNode* reverseList(struct ListNode* head) {if (head == NULL) {return NULL;}ltnode* p1 = NULL, *p2 = head, *p3 = head->next;while (p2) {p2->next = p1;p1 = p2;p2 = p3;if (p3)p3 = p3->next;}return p1;}bool chkPalindrome(ListNode* A) {// write code here//思路：先找到链表的中间节点，从中间开始向后反转链表，看反转后的链表是否与原来的链表相同ltnode* midnode = middleNode(A);ltnode*revs=reverseList(midnode);ltnode*pcur1=A,*pcur2=revs;while(pcur2){if(pcur2->val!=pcur1->val){return false;}pcur2=pcur2->next;pcur1=pcur1->next;}return true;}

除了这种思路，还有没有啥比较简单的思路呢？

有的兄弟们，有的。

我们注意到，题目中特地提醒我们了：链表的长度不大于900，这就让我们有了可乘之机。我们可以将链表转化为数组，然后这个题目就转换为了判断数组是否是回文结构，这就简单多了呀，既如此，快来上手写代码：

typedef struct ListNode ltnode;bool chkPalindrome(ListNode* A) {// write code hereint arr[900];int size=0;//表示数组中有效数据个数ltnode*pcur=A;while(pcur){arr[size++]=pcur->val;pcur=pcur->next;}//将链表转换为数组之后，就开始判断数组是否是回文结构int left=0,right=size-1;while(left<=right){if(arr[left]!=arr[right]){return false;}right--;left++;}return true;}

这个思路可就简单太多了，但是这是因为题目让我们抓住了漏洞，如果题目没有告诉我们链表的最大长度，那就目前只能使用方法一了，这是最保险的方法。

• 138. 随机链表的复制 - 力扣（LeetCode）

假设没有random指针，就是普通的来链表，要让我们复制一份，我们就只需要创建节点，为每个节点的val对应赋值，指定next指针的指向即可。而这道题最大的难点就是找到拷贝后每个节点的random指针应该指向哪里。

可以想一下：我们能否利用原链表去找到我们要复制的目标链表中每个节点的random指针的指向？

我们可以在原来链表中的每个节点之间插入一个新的节点，这个节点的值与它前一个节点的值相同，如图：

这样一来，我们就不难发现，我们插入节点的random指针应该指向的节点与它前一个节点的random节点的next指针指向的节点。也就是说原链表中节点A的random指针的next指针的指向就是A的next指针指向的节点（插入节点）的random指针的指向。

所以，这道题的思路就是：先插入新节点，为新节点的random指针指定指向，将新节点从原链表中割除并连成新链表。

分析了这么多，终于能开始写代码了：

typedef struct Node node;//创建新节点node* buynode(int val){node*newnode=(node*)malloc(sizeof(node));newnode->val=val;return newnode;}
struct Node* copyRandomList(struct Node* head) 
{if(head==NULL){return head;}//将新节点插入到原链表node* pcur=head;node*newnode;while(pcur){newnode=buynode(pcur->val);newnode->next=pcur->next;pcur->next=newnode;pcur=newnode->next;}//为新节点的random指针指定指向:新节点random指针的指向是他的前一个节点random指针的next指针指向的节点pcur=head;newnode=head->next;while(pcur){if(pcur->random){newnode->random=pcur->random->next;}else{newnode->random=NULL;}pcur=newnode->next;if(pcur)newnode=pcur->next;}//将新的链表的节点连接起来：node* newhead=head->next;node* newtail=newhead;pcur=newtail->next;while(pcur){newtail->next=pcur->next;newtail=newtail->next;pcur=newtail->next;}return newhead;
}

今天的oj练习题就讲到这里，数据结构部分小伙伴们一定要好好刷题呀！！！