C语言.数据结构.单链表经典算法

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

题目：移除链表元素

1.1题目描述：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

1.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    //创建一个新的空链表来装不为val节点：
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;

    ListNode* pcur = head;
    //找不为val值的节点尾插在空链表中
    while(pcur) {
        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;
}
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

1.3图文解释：

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

题目：反转链表

2.1题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

2.2题解：

/**
 * 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 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head->next;
    //遍历单链表：
    while(n2) {
        //发生反转：改变指针指向
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3) {
            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
29

2.3图文解释

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

题目：合并两个有序链表

3.1题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

3.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    //判断两个链表是否有空链表出现：
    if(list1 == NULL)
    {
        //证明只有list2存在并且list2本身就是有序的，所以不用合并了
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    //创建一个带哨兵位的链表，节省判新链表是否为空
    ListNode* newhead, *newtail;
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* l1 = list1;
    ListNode* l2 = list2;

    //开始合并：
    while(l1 && l2)
    {
        if(l1->val > l2->val)//哪个节点小，哪个节点就先排序
        {
            newtail->next = l2;
            newtail = newtail->next;
            //l2也得往下走
            l2 = l2->next;
        }
        else
        {
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;
        }
    }
    //走到这 就会有指针越界访问了,但是还没有把所有的节点尾插在新链表中
    if(l1)
    {
        newtail->next = l1;
    }
    if(l2)
    {
        newtail->next = l2;
    }
    //哨兵位 什么都不表示，有效位置为哨兵位的下一个位置
    ListNode* ret = newhead->next;
    //把哨兵位内存空间释放掉
    free(newhead);
    newhead = NULL;
    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
57
58

3.3图文解释

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

题目：链表的中间节点

4.1题目描述：

• 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
• 如果有两个中间结点，则返回第二个中间结点。

4.2题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    //定义两个快慢指针：
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        //slow走一步，fast就走两步（一个快，一个慢）
        slow = slow->next;
        fast = fast->next->next;
    }
    //走到这里 正好slow指向了链表的中间位置，两种情况都成立
    return slow;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.3图文解释

5.经典算法OJ题5：环形链表的约瑟夫问题

题目：环形链表的约瑟夫问题

• 著名的Josephus问题
  据说著名犹太 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须人杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
  然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

5.1题目描述：

• 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
  下一个人继续从 1 开始报数。
  n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？
• 数据范围：
  1 ≤
  声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/716169