系列文章目錄
文章目錄
- 系列文章目錄
- 前言
- 一、調整奇偶數順序
- 1.題目描述
- 2.解題思路
- 二、移除鏈表元素
- 1.題目描述
- 2.解題思路
- 三、反轉鏈表
- 1.題目描述
- 2.解題思路
- 總結
前言
一、調整奇偶數順序
調整奇偶數順序使奇數位于偶數前面
1.題目描述
輸入一個整數陣列，實作一個函式來調整該陣列中數字的順序，使得所有奇數位于陣列的前半部分，所有偶數位于陣列的后半部分，
2.解題思路
- malloc創建一塊空間
- 遍歷陣列兩遍，第一遍只存盤奇數，第二遍只存盤偶數，
代碼如下：
int* exchange(int* nums, int numsSize, int* returnSize)
{
int i=0;
int s=0;
int* str=(int*)malloc(sizeof(int)*numsSize);
*returnSize=numsSize;
for(i=0;i<numsSize;i++)
{
if(nums[i]%2==1)
{
str[s]=nums[i];
s++;
}
}
for(i=0;i<numsSize;i++)
{
if(nums[i]%2==0)
{
str[s]=nums[i];
s++;
}
}
return str;
}
二、移除鏈表元素
移除鏈表元素
1.題目描述
給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，
2.解題思路
1.設定哨兵結點法：不用判斷第一個值是否為val
代碼如下：
struct ListNode* RemoveElements(struct ListNode* head, int val)
{
struct ListNode* guardhead = (struct ListNode*)malloc(sizeof(struct ListNode*));
guardhead->next = head;
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->next == val)
{
struct ListNode* next = cur->next;
prev->next = next;
free(cur);
cur = next;
}
else
{
prev = cur;
cur = cur->next;
}
}
guardhead->next = head;
free(guardhead);
return head;
}
2.不設定哨兵結點法：判斷第一個值為val和第一個值不為val的情況
第一個值是val圖解:
第一個值不為val圖解:
代碼如下：
struct ListNode* RemoveElements(struct ListNode* head, int val)
{
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while (cur)
{
struct ListNode* next = cur->next;
if (cur->next == val)
{
if (prev == NULL) //第一個結點的值就是val
{
free(cur);
head = next;
cur = next;
}
else
{
prev->next = next;
free(cur);
cur = next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
}
三、反轉鏈表
反轉鏈表
1.題目描述
定義一個函式，輸入一個鏈表的頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點，
2.解題思路
1.三指標法：定義指標1為NULL，定義指標2為head指標，定義指標3為head->next
代碼如下：
struct ListNode* reverseList(struct ListNode* head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;
while (n2)
{
//翻轉
n2->next = n1;
//迭代
n2 = n3;
n1 = n2;
if (n3)
{
n3 = n3->next;
}
}
return n1;
}
2.頭插法:取原鏈表的結點依次頭插到鏈表中
代碼如下：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
總結
本文僅僅簡單介紹了鏈表常見的兩題，這些題目我們以后可能會遇到，我們務必掌握，另外，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/276234.html
標籤：其他