单链表专题---暴力算法美学(2)(有视频演示）

1.4 合并两个有序链表

/*** 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=NULL;//比大小while(l1 && l2)//其中一个走到空都要结束循环{if(l1->val < l2->val){//如果newHead为空if(newHead ==NULL){newHead=newTail=l1;}else{newTail->next=l1;newTail=newTail->next;}//把l1指向的数值拿来插入新链表l1=l1->next;}else{if(newHead==NULL){newHead=newTail=l2;}else{newTail->next=l2;newTail=newTail->next;}//把l2指向的数值拿下来插入l2=l2->next;}}if(l1){newTail->next=l1;}if(l2){newTail->next=l2;}return newHead;
}

代码优化一下！

/*** 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=l1;newTail=newTail->next;//把l1指向的数值拿来插入新链表l1=l1->next;}else{newTail->next=l2;newTail=newTail->next;//把l2指向的数值拿下来插入l2=l2->next;}}if(l1){newTail->next=l1;}if(l2){newTail->next=l2;}//动态申请的空间要释放掉ListNode* ret=newHead->next;free(newHead);newHead=NULL;return ret;
}

视频讲解

1.5 环形链表的约瑟夫问题

思路：1.创建带环链表

           2.计数

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) {//1.根据n创建带环链表ListNode* prev = createCircle(n);ListNode* pcur = prev->next;int count = 1;//当链表中只有一个节点的时候结束循环while (pcur->next != pcur) {if (count == m) {//销毁pcur节点prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;} else {//此时不用销毁节点prev = pcur;pcur = pcur->next;count++;}}//此时剩下一个节点就是要返回的节点里面的值return pcur->val;}

1.6 面试题：02.04 分割链表

思路：1.创建一个大链表和一个小链表：

           2.遍历原链表，大于或等于x 的节点插入大链表，小于x的节点插入小链表：

           3.小链表的尾结点链接大链表的第一个有效节点

/*** 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;}//创建两个链表，一个大链表，一个小链表，大链表放大于或者等于x的值，小链表放小于x的值ListNode* lessHead,* lessTail;ListNode* greaterHead,* greaterTail;lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));//遍历原链表，大链表放大于或者等于x的值，小链表放小于x的值ListNode* pcur=head;while(pcur){//大于x的值插入大链表if(pcur->val >= x){greaterTail->next=pcur;greaterTail=greaterTail->next;}else{//小于x的值插入小链表lessTail->next=pcur;lessTail=lessTail->next;}pcur=pcur->next;} greaterTail->next=NULL;//如果不加这一行代码会出现死循环+ next指针初始化//小链表的尾节点链接大链表的第一个有效的节点lessTail->next=greaterHead->next;ListNode* ret=lessHead->next;free(lessHead);free(greaterHead);lessHead=greaterHead=NULL;return ret;
}

博主的上一篇博客：单链表专题---暴力算法美学(1)(有视频演示）-CSDN博客