顺序表和链表的8道算法题

移除元素

题目连接放这了https://leetcode.cn/problems/remove-element/

思路一

创建一个新数组：首先遍历原数组的所有数据，把不等于val的值直接放在新数组里，然后返回新数组的长度。由于这个思路不符合题目的要求，所以我们不采用这个解法，这个思路仅作拓展！！！

int removeElement(int* nums, int numsSize, int val)
{
    int n1, n2;
    n1 = n2 = 0;
    int arr[numsSize];
    while (n2 < numsSize)
    {
        if (nums[n2] != val)
        {
            arr[n1] = nums[n2];
            n1++;
        }
        n2++;
    }
    return n1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

思路二

使用两个临时变量n1和n2，n2负责遍历数组，n1负责将不等于val的值重新赋值给数组，最后n1就是新数组的下标

这是原数组：

开始进行遍历和赋值操作：

int  removeElement(int* nums, int  numsSize, int  val)
{
 int n1, n2;
n1 = n2 = 0;
 while(n2 < numsSize)
    {
 if(nums[n2] != val)
        {
 nums[n1] = nums[n2];
            n1++;
        }
        n2++;
    }
 return n1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并两个有序数组

题目连接放这了https://leetcode.cn/problems/merge-sorted-array/

思路

由于数组nums1有足够的空间，所以我们选择将两个合并的数组就直接放在数组nums1中，现在我们要考虑如何存放，由于两个数组是有序的并且是递增的，存放也是要求递增，所以我们要么从两个数组的首元素开始遍历比较进行存放，要么从两个数组的尾元素开始遍历比较进行存放。

如果从首元素开始遍历存放，比较得到最小的元素，存放在nums1的第一个位置进行存放（因为最后得到的数组元素也要递增排列，所以要从nums1的第一个位置开始存放）；这时候就有一个问题了，nums1前面几个原先的元素可能就找不到了，我们举个例子：nums1=[1,2,3,0,0,0]，nums2=[0]，开始比较，nums2的0小于nums1的1，那nums1的第一个元素1就会被0覆盖掉，导致元素丢失，为了避免这个情况，我们就需要保存这个元素，可是我们不知道要几个变量来保存元素，毕竟nums1有多少的元素比nums2大是不确定的，所以这个方法就比较难实现。

因此我们考虑从尾部开始遍历存放，这时候我们需要三个临时变量，两个变量是分别从两个数组的尾元素进行遍历，剩下一个变量是从nums1最后一个空间开始来进行赋值存放元素的操作。

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
    int l1, l2, l3;
    l1 = m - 1;
    l2 = n - 1;
    l3 = m + n - 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--];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

这里稍微解释一下循环遍历条件，首先第一个循环结束条件肯定是两个下标不能小于0，否则会发生数组的越界访问！！！从这个循环条件出来有两种情况，一是l1<0，二是l2<0，为什么不能是两个同时小于0，因为有一个数组会被最先遍历完，然后就会跳出循环，不可能发生两个数组同时遍历完的！！！
跳出循环后，题目要求把nums2合并到nums1中，所以当l2>=0时，说明nums2是没有遍历完的，我们只需要处理这一个条件即可，不用担心nums1了，因为跳出第一个循环后，如果l2>=0，说明nums1数组已经遍历完了，所以不需要考虑nums1了。

移除链表元素

题目连接：https://leetcode.cn/problems/remove-linked-list-elements/

思路一

遍历原链表，将val的节点就地删除。

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* prev, * pcur;
    prev = pcur = head;
    ListNode* next;
    while (pcur)
    {
        if (pcur->val == val)
        {
            next = pcur->next;
            prev->next = next;
            pcur = next;
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
        }
    }
    if (head->val == val)
    {
        return head->next;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

这里我们要注意了不用free是因为这时OJ题，如果没有特别说明，我们不需要free，当然你也可以free
还有题目有说可能会出现空链表的情况，这个我们需要单独处理。
在循环中我们是无法删除第一个节点的，所以后面我就用来一个判断来专门处理了一下。

思路二

创建新的链表，将不含val 的节点进行尾插即可。

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* NewHead, * NewTail;
    NewHead = NewTail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* ptail = head;
    while (ptail)
    {
        if (ptail->val != val)
        {
            //尾插
            NewTail->next = ptail;
            NewTail = NewTail->next;
        }
        ptail = ptail->next;
    }
    NewTail->next = NULL;
    ListNode* next = NewHead->next;
    free(NewHead);
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

这里隆重介绍一下哨兵位，哨兵位就是头结点，它不存放任何有效的数据，就是一个站岗的功能，有了哨兵位，我们就可以直接进行尾插操作，而不是要单独处理新链表尾空的情况，比较方便，题目要求我们放回第一个有效的节点地址，也很简单，直接放回哨兵位的next就可以了。
然后我们还要注意一下如果原链表为空的时候，我们需要单独处理的。

反转链表

题目连接：https://leetcode.cn/problems/reverse-linked-list/

思路一

创建新链表，使用头插操作就可以实现链表的反转。

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* NewHead, * NewTail;
    NewHead = NewTail = (ListNode*)malloc(sizeof(ListNode));
    NewTail->next = NULL;//先置为空，便于最后一个节点指向NULL
    ListNode* ptail = head;
    ListNode* next;
    while (ptail)
    {
        next = ptail->next;//保存下一个节点
        NewTail = NewHead->next;//保存新链表原先的第一个节点
        NewHead->next = ptail;//头插
        ptail->next = NewTail;//将新的第一个节点和原先的第一个节点进行连接
        ptail = next;//继续遍历
    }
    next = NewHead->next;
    free(NewHead);
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

思路二

原链表进行操作，改变每一个节点的指向，如下图所示：

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* l1, * l2;
    l1 = head;
    l2 = head->next;
    l1->next = NULL;//先将第一个节点的指向置为NULL
    while (l2)
    {
        ListNode* next = l2->next;//保存下一个节点
        l2->next = l1;
        l1 = l2;
        l2 = next;
    }
    return l1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

合并两个有序的链表

题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/

思路

创建新链表，遍历两个链表的所有的节点，然后尾插到新链表里。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    ListNode* NewHead, * NewTail;
    NewHead = NewTail = (ListNode*)malloc(sizeof(ListNode));
    NewHead->next = NULL;//处理空链表的情况
    ListNode* l1, * l2;
    l1 = list1;
    l2 = list2;
    while (l1 && l2)
    {
        if (l1->val < l2->val)
        {
            NewTail->next = l1;
            l1 = l1->next;
            NewTail = NewTail->next;
        }
        else
        {
            NewTail->next = l2;
            l2 = l2->next;
            NewTail = NewTail->next;
        }
    }
    if (l1)
    {
        NewTail->next = l1;
    }
    if (l2)
    {
        NewTail->next = l2;
    }
    ListNode* next = NewHead->next;
    free(NewHead);
    return next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

这里我将哨兵位的next置为NULL，是因为如果两个链表都是空的话，就会放回NULL，也就少写了一些判断语句。
当循环走出去后，一定有一个链表还没有走完，所以直接进行该链表与新链表连接即可，不需要一个节点一个节点的插入，因为剩下的链表本来就是有序的~~

链表的中间节点

题目连接：https://leetcode.cn/problems/middle-of-the-linked-list/

思路

快慢指针，定义两个指针，一个快指针每次走两步，一个慢指针每次走一步，最后快指针遍历完链表的所有节点之后，慢指针就是链表的中间节点
原理就是：2slow = fast

讨论一下循环结束的条件，当有奇数个节点时：

很显然fast->next==NULL时要跳出循环。

当有偶数个节点时：

当fast==NULL时跳出循环。

现在思考是写while(fast->next && fast) 还是写 while(fast && fast->next)，还是两个都可以？

typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
    ListNode* slow, * fast;
    slow = fast = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12

公布答案，只能写while(fast && fast->next)，两个顺序不能变换，因为如果fast为NULL时，你先写的fast->next会对空指针进行非法访问！！！

环形链表的约瑟夫问题

题目链接：https://www.nowcoder.com/share/jump/9257752291712999799127

思路

这里我们可以使用循环链表来进行操作，循环链表是指头尾节点是相连的：

有了循环链表之后，我们就可以进行删除节点的操作，最后会剩下一个节点，这个节点的next就是它自己，所以循环结束条件就是这个。
用一个计数器来查看是否要进行删除操作，两个指针进行遍历链表，一个保存上一个节点，一个则往前走，一直到循环结束，所以我在创建循环链表这个函数采用放回尾节点，这样便于一开始我们直接拿到头节点和尾节点，方便后续的操作。

typedef struct ListNode ListNode;
ListNode* BuyNewnode(int x)//创建新节点
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

ListNode* CreatList(int n)//创建循环链表
{
    ListNode* head, * tail;
    head = BuyNewnode(1); //创建第一个节点
    tail = head;
    for (int i = 2; i <= n; i++)
    {
        ListNode* newnode = BuyNewnode(i);
        tail->next = newnode;
        tail = tail->next;
    }
    tail->next = head;//首尾相连
    return tail;
}

int ysf(int n, int m)
{
    int count = 1;
    ListNode* pcur, * prev;
    //创建循环链表
    prev = CreatList(n);
    pcur = prev->next;
    while (prev != prev->next)
    {
        if (count == m)//删除节点
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    int ret = prev->val;
    free(prev);
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

分割链表

题目链接：https://leetcode.cn/problems/partition-list-lcci/

思路：

我们可以创建两个新链表，一个小链表存放小于x的节点，另一个大链表存放大于或等于x的节点，最后将两个链表合并，放回小链表的头指针即可。

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{
    if (head == NULL)
    {
        return head;
    }
    ListNode* LessHead, * LessTail;
    ListNode* BigHead, * BigTail;
    //创建哨兵位
    LessHead = LessTail = (ListNode*)malloc(sizeof(ListNode));
    BigHead = BigTail = (ListNode*)malloc(sizeof(ListNode));

    ListNode* ptail = head;
    while (ptail)
    {
        if (ptail->val < x)
        {
            LessTail->next = ptail;
            LessTail = LessTail->next;
        }
        else
        {
            BigTail->next = ptail;
            BigTail = BigTail->next;
        }
        ptail = ptail->next;
    }
    BigTail->next = NULL;//将大连表的尾节点置为NULL
    LessTail->next = BigHead->next;
    return LessHead->next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

这里要注意你要将大链表的尾节点置为NULL，因为你不确定大链表的尾节点的next是否还指向其他节点！！！
我这里没有删除哨兵位，如果你想删除也可以。