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

接着我们介绍后面的三道题，虽然代码变多了但我们的思路更加通顺了

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

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

创建新链表，遍历原链表，将节点值小的进行尾插到新链表中

这里要多次进行对NULL的判断，开始传入列表，中间newHead的判断，循环出来一个为NULL的判断



重复原因：新链表存在空链表和非空两种情况
优化的方法：
1.将重复的部分封装成一个函数
2.动态申请一个空间但这个空间部存储任何的信息
那么我们着重讲一下第二个方法：

他的解决方法就是让新链表不为NULL
在创建时动态申请一块空间，但不存储任何数据，让NULL节点变为非NULL的节点，这是就不用判断链表是不是为非NULL

但这时返回就不能将头节点直接返回，而是要将头节点的下一个位置的地址返回

当然释放的空间还是要释放一下，来使代码更加完善

/**
 * 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) {
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    //判空
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }

    ListNode* newHead,*newTail;
    //newHead = newTail = NULL;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
    
    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            newTail->next = l1;
            newTail = newTail->next;
            l1 = l1->next;
        }
        else
        {
            newTail->next = l2;
            newTail = newTail->next;
            l2 = l2->next;
        }
    }
    //跳出循环有两种情况
    if(l2 != NULL)
    {
        newTail->next = l2;
    }
    if(l1 != NULL)
    {
        newTail->next = l1;
    }
    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

其实这样的链表叫带头链表，这个“头”一般称作哨兵位

5. 循环链表经典应⽤-环形链表的约瑟夫问题

题目链接：https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a

思路一：用数组的方法，先进行遍历然后将离开的人置为0，然后不断循环遍历最中不为0的就是我们要的数据
思路二：循环链表的方法
我们先介绍一下循环链表：

这里涉及到循环链表，其实也就是单链表但是尾部相连了
那么在创建和删除时要多注意就行了

循环数数，将数到2的，将其删除

这里就要使用前后指针

代码的难点就是创建循环链表

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 #include <stdio.h>
typedef struct ListNode ListNode ;
 ListNode* buyNode(int x)//申请空间
 {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if(node == NULL)
    {
        exit(1);
    }
    node->val = x;
    node->next = NULL;
    return node;
 }

 ListNode* createCircle(int n)//创建带环链表
 {
    //创建第一个节点
    ListNode* phead = buyNode(1);
    ListNode* ptail = phead;
    for(int i = 2; i <= n;i++)
    {
        ptail->next = buyNode(i);
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
 }
int ysf(int n, int m ) {
    // write code here
    ListNode* prev = createCircle(n);
    ListNode* pcur = prev->next;
    int count = 1;
    while (prev->next != pcur)//链表只有一个节点 
    {
        if(count == m)
        {
            //销毁，先连接，在销毁
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else 
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}
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
59

6. 单链表相关经典算法OJ题5：分割链表

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


思路一：将原列表复制一份，然后对大于等于x的进行操作，先尾插后销毁

思路二：或者创建一个新链表进行存储，对大于的数进行尾插，小于的进行头插

思路三：创建两个新链表：小链表和大链表

分成两个链表然后将两个链表连接起来



这里就是greaterHead后的指针不为NULL，而是一个随机地址

将两个代码换过来，就可以解决这个问题了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)
    {
        return head;
    }
    ListNode* lessHead,*lessTail;
    ListNode* greaterHead,*greaterTail;
    lessHead = lessTail =(ListNode*)malloc(sizeof(ListNode));
    greaterHead = greaterTail =(ListNode*)malloc(sizeof(ListNode));

    //遍历原链表，进行尾插
    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;
    }
    //首尾相连
    greaterTail->next = NULL;
    lessTail->next = greaterHead->next;
    

    ListNode* ret = lessHead->next;
    free(lessHead);
    free(greaterHead);
    lessHead = greaterHead = 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