C语言简单的数据结构：单链表的有关算法题（1）

算法题重点在于思路，代码其实并不难，这里的每一题都提供多种思路，大家可以动手写一下，并找到更好的解题方法
这里先介绍前三道

1.单链表相关经典算法OJ题1：移除链表元素

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

删除链表的指定元素
思路一：

让pcur找到要删除的元素，但是这样没法让链表连接，我们要在新建一个变量，来进行相连，还要有一个变量将pcur->next存下来，来释放pcur


思路二：
找值不为val的值然后将，尾插到新链表中

我们对这个方法进行代码实现：

此时运行

这里发现6并没有删除掉，原因就是5的节点仍然指向下一个节点

但这时又有问题了，我们对NULL指针进行解引用了，加一个判断如果newTail为NULL就部置NULL了

此时提交就通过了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    // 创建新链表的头和尾
    ListNode* newHead = NULL;
    ListNode* newTail = NULL;

    ListNode* pcur = head;
    while (pcur) 
    {
        if (pcur->val != val) 
        {
            if (newHead == NULL) // 链表为NULL
            {
                newHead = newTail = pcur;
            } else 
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newTail)
        newTail->next = NULL;
    return newHead;
}
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

2.单链表相关经典算法OJ题2：反转链表

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

思路一：
创建新链表，将原来的数据进行头插入

思路二：
创建3个指针完成原链表的反转

创建三个指针n3指向n1，然后三个指针都向后走，再加上部分NULL的判定即可
1.n3走到NULL时就不能向下走了
2.链表为NULL就不能运行直接返回

这里提交即可

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //判空
    if(head == NULL)
    {
        return head;
    }
    ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//如果n3不为NULL就继续向下
            n3 = n3->next;
    }
    return n1;
}
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

3. 单链表相关经典算法OJ题4：链表的中间结点

相关链接：https://leetcode.cn/problems/middle-of-the-linked-list/

找到中间点，如果有两个中间点就是后一个
思路一：
遍历，count计算节点数，返回（count/2）的next节点
思路二：
快慢指针
创建两个指针让快指针刚好时慢指针的2倍，此时出现一下情况

思路理解了代码就好写了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

多画图，多分析，多尝试写代码相信你会有所收获的，加油！！！