数据结构：合并两个有序链表约瑟夫问题详解（C语言实现 + 图解思路）

1，合并两个有序链表

/** * 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) { return list2; } if (list2 == NULL) { return list1; } // 申请新链表 ListNode* l1 = list1; ListNode* l2 = list2; ListNode *newhead, *newtail; newhead = newtail = (ListNode*)malloc(sizeof(ListNode)); // 遍历旧链表 while (l1 && l2) { if (l1->val > l2->val) { newtail->next = l2; newtail = l2; l2 = l2->next; } else { newtail->next = l1; newtail = l1; l1 = l1->next; } } // 跳出是是l1，l2有一个是走到NULL了 if (l1) { newtail->next = l1; } if (l2) { newtail->next = l2; } ListNode* ret = newhead->next; free(newhead); newhead = NULL; return ret; }

注意

这是申请带头节点

可以减少重复代码

否则要检查newtail为NULL的时候

还有出了while之后

就直接在newtail-->next = 还没走完的就行

因为本身就是成型的链表

2，自杀游戏--循环链表--约瑟夫问题

//自杀游戏 struct ListNode { int val; struct ListNode* next; }; typedef struct ListNode ListNode; //BuyNode一下创建节点 ListNode* BuyNode(int x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); if (node == NULL) { exit(1); } node->val = x; node->next = NULL; return node; } //成环函数 ListNode* CreatCircle(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) { ListNode* prev = CreatCircle(n); ListNode* pcur = prev->next; //从pcur开始数的 int count = 1; while (pcur->next = pcur) //while (prev->next = prev)这个行不行 { if (count == m) { //销毁pcur节点 prev->next = pcur->next; free(pcur); pcur = prev->next; count = 1; } else { //此时不需要销毁节点 prev = pcur; pcur = pcur->next; count++; } int a = pcur->val; free(pcur); pcur = NULL; return a; } }

注意的是

pcur和prev作用

在销毁pcur的时候，需要前一个节点链接pcur->next;

所以就有了prev

因为成环使用BuyNode 所以有函数BuyNode