🔥铅笔小新z：个人主页
🎬博客专栏：数据结构
💫滴水不绝，可穿石；步履不休，能至渊。

---

一、顺序表经典算法题

1.1 经典算法OJ题1：移除元素

解题思路：

双指针法：

先创建两个变量：src,dst，让这两个变量都指向数组首元素。

如果src指向的值等于val，则src++，若不等于则将src的值赋给dst，然后src++，dst++。

最后当src走到数组末尾时循环结束。

参考代码：

int src = 0;
int dst = 0;
while(src < numsSize)
{
    if(nums[src] == val)
    {
        src++;
    }
    else
    {
        nums[dst++] = nums[src++];
    }
}
return dst;

---

1.2 经典算法OJ题2：合并两个有序数组

从题目中我们可以知道nums1数组的大小是可以共同容纳nums1和nums2所有有效数字的，所以我们有一种方法就是将nums2的数字存到nums1中，但题目中要求合并后的数组按非递减顺序排列，这里我就来讲一讲具体的解题思路：

解题思路：

首先定义三个变量：l1, l2, l3，l1指向nums1数组最后一个元素，l2指向nums2数组最后一个元      素，l3指向nums1数组的末尾。

然后将l1和l2进行比较，谁大谁就放在l3的位置然后l3--，l1或者l2进行--。

这样最后会出现两种情况：

一种是l1先走完但是l2没有走完，导致l2中的数字没有完全被放在l1中。

另一种是l2先走完，这种情况不影响最后的结果。

所以我们要在程序后面判断一下出现了哪种情况。

参考代码：

int l1 = m - 1;
int l2 = n - 1;
int l3 = nums1Size - 1;
while (l1 >= 0 && l2 >= 0)
{
    if (nums1[l1] >= nums2[l2])
    {
        nums1[l3--] = nums1[l1--];
    }
    else
    {
        nums1[l3--] = nums2[l2--];
    }
}
while (l2 >= 0)
{
    nums1[l3--] = nums2[l2--];
}

---

二、链表经典算法题

2.1 单链表经典算法OJ题1：移除链表元素

解题思路：

既然要删除某一元素，我们不妨新建一个新的链表，然后遍历原链表把值不为val的元素存到新的链表当中。

参考代码：

//创建新链表
struct ListNode* newhead, *newtail;
newhead = newtail = NULL;
//遍历原链表
struct ListNode* pcur = head;
while(pcur)
{
    //找值不为val的值，尾插到新链表中
    if(pcur->val != val)
    {
        //判断新链表是否为空
        if(newhead == NULL)
        {
            newhead = newtail = pcur;
        }
        //新链表不为空
        else
        {
            newtail->next = pcur;
            newtail = newtail->next;
        }
    }
    pcur = pcur->next;
}
if(newtail)
    newtail->next = NULL;
return newhead;

---

2.2 单链表经典算法OJ题2：反转链表

解题思路：

首先如图，我们创建三个指针：n1, n2, n3，然后利用这三个指针分别将各个元素的指向进行反转进而完成对链表的反转。

那么我们就应该让n2的next指针指向n1，然后n1到n2的位置，n2到n3的位置，n3再向后挪一位，知道n2走到最后即为NULL.

参考代码：

//判空
if(head == NULL)
    return head;
//创建三个指针
struct ListNode* n1, n2, n3;
n1 = NULL, n2 = head, n3 = n2->next;
while(n2)
{
    n2->next = n1; 
    n1 = n2;
    n2 = n3;
    if(n3)
        n3 = n3->next;
}
return n1;

---

2.3 单链表经典算法OJ题3：合并两个有序链表

解题思路：

做这道题的大体思路就是我们创建一个新的链表，然后遍历比较两个链表各个元素的值的大小，将小的元素放在新的链表中。

具体思路就是我们创建新的链表时应该先创建一个哨兵位，然后将两个链表的元素以哨兵位为头依次放在其后面。

创建两个变量l1, l2分别指向第一个链表和第二个链表，将l1和l2指向的元素的值进行比较，小的放在新链表中，然后将其向后移一位再进行比较。

参考代码：

    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = 0;
    head->next = NULL;
    struct ListNode* tail = head;
    while(l1 && l2)
    {
        if(l1->val <= l2->val)
        {
            tail->next = l1;
            tail = tail->next;
            l1 = l1->next;
        }
        else
        {
            tail->next = l2;
            tail = tail->next;
            l2 = l2->next;
        }
    }
    if(l2 == NULL)
    {
        tail->next = l1;
    }
    else
    {
        tail->next = l2;
    }
    return head->next;

---

2.4 单链表经典算法OJ题4：链表的中间节点

解题思路：

这道题简便的算法就是利用快慢指针。

定义两个指针：slow, fast，都指向链表的第一个元素，慢指针一次走一步，快指针一次走两步，直到fast = NULL或fast->next = NULL，此时slow对应的元素就是中间节点。

！！！这里要特别注意的是判断循环结束的条件是（fast && fast->next），两者不能调换位置，因为如果调换位置，fast走到NULL时，fast->next就会报错，因为不能对空指针解引用。

参考代码：

    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }   
    return slow; 

---

2.5 单链表经典算法OJ题5：分割链表

解题思路：

我们可以创建两个新链表：一个小链表用于存储小于x的节点，大链表用于储存大于等于x的链表，最后将小链表的尾指针的next指向大链表的第一个有效元素。

参考代码：

//判空
if(head == NULL)
{
    return head;
}
//创建两个带头链表
struct ListNode* lesshead, *lesstail;
struct ListNode* greaterhead, *greatertail;
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));

//遍历原链表，将原链表中的节点尾插到大小链表中
struct ListNode* pcur = head;
while(pcur)
{
    //尾插到小链表中
    if(pcur->val < x)
    {   
        lesstail->next = pcur;
        lesstail = lesstail->next;
    }
    //尾插到大链表中
    else
    {
        greatertail->next = pcur;
        greatertail = greatertail->next;
    }
    pcur = pcur->next;
}
greater->next = NULL;
lesstail->next = greaterhead->next;
return lesshead->next;

---

2.6 循环链表经典应用：环形链表的约瑟夫问题

解题思路：

我们的分析思路根据上面的图，首先我们要创建一个首尾相连的环形表，然后将将prev指向末尾元素，便于我们后面进行向后移动，pcur指向末尾元素即首元素，然后我们用count开始计数，从首元素开始，count = 1，假设报数m为2，然后prev和pcur向后移动一位，此时count++，count == m，所以我们要删除pcur指向的元素，怎么删除呢，我们要将prev->next指向pcur->next，然后free(pcur)，再用pcur = prev->next为pcur重新赋值，直到最后剩下数字3为止，此时循环结束的条件是pcur == pcur->next。

参考代码：

typedef struct ListNode LN;

LN* applycapa(int i)
{
    LN* head = (LN*)malloc(sizeof(LN));
    head->val = i;
    head->next = NULL;
    return head;
}
//创建带环链表
LN* createCircle(int n)
{
    //创建头节点
    LN* head = applycapa(1);
    LN* tail = head;
    //创建链表
    for(int i = 2; i <= n; i++)
    {
        tail->next = applycapa(i);
        tail = tail->next;
    }
    tail->next = head;
    return tail;
}
int ysf(int n, int m ) 
{
    LN* prev = createCircle(n);
    LN* pcur = prev->next;
    int count = 1;
    while(pcur != pcur->next)
    {
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 0;
        }
        else 
        {
            prev = pcur;
            pcur = pcur->next;
        }
        count++;
    }
    return prev->val;
}

---