上篇博客中，我们学习了单链表，为了更加熟练掌握这一知识点，就让我们将单链表的应用操练起来吧！
思路一：遍历原链表，将值为val的节点释放掉。
/** * 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,*newTail; newHead=newTail=NULL; //遍历原链表 while(pcur) { //找值不为val的值，插入到新链表中 if(pcur->val!=val) { //链表为空 if(bewHead==NULL) { newHead=newTail=pcur; } else{ //链表不为空 newTail->next=pcur; newTail=newTail->next; } } pcur=pcur->next; } if(newTail){ newTail->next=NULL; } return newHead; }
思路一：遍历原链表，将原链表的节点头插。
思路二：
创建三个指针，完成链表的翻转
/** * 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=n3->next; } } return n1; }
思路一：直接返回node/2
思路二：快慢指针，slow每次走一步，fast每次走两步
/** * 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) { if(newHead==NULL) { newHead=newTail=l1; } else { newTail->next=l2; newTail->next=newTail; } l2=l2->next; } } if(l2) { newTail->next=l2; } if(l1) { newTail->next=l1; } (ListNode*)ret=newHead->next; free(newHead); return ret;//newHead里面没有存储值 }
存在重复代码，如何优化呢？
我们可以定义一个头结点，也就是哨兵位。这个链表实际叫作带头链表。
环形链表的约瑟夫问题_牛客题霸_牛客网 (nowcoder.com)
第一步 创建带环链表
第二部 遍历带环链表
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param n int整型 * @param m int整型 * @return int整型 */ 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* creatCirle(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=creatCirle(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;//重新报数，count重新记为初始值 } else {//不需要销毁节点 prev=pcur; pcur=pcur->next; count++; } } //当链表中只有一个节点的情况跳出循环 return pcur->val; }
面试题 02.04. 分割链表 - 力扣（LeetCode）
思路一：在原链表上修改
若pcur的节点小于x，往后走
若pcur的节点大于或等于x，尾插在原链表后，删除旧节点
思路二：创建新链表，遍历原链表。若pcur的节点小于x，让它头插在新链表中。
若pcur的节点值大于或等于x，尾插。
思路三：创建新链表，小链表和大链表。
将小链表的尾结点和大链表的第一个有效节点首位相连。
typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x){ if(head==NULL) { return NULL; } 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; } //小链表的尾结点和大链表的头结点相连 greaterHead->next=NULL;//若不写这一行，则代码出现死循环+next指针初始化 lessTail->next=greaterHead->next; ListNode*ret=lessHead->next; free(lessHead); free(lessTail); lessHead=lessTail=NULL; return ret; }
链表的分类
带头：是指链表带有哨兵位，即为头结点。
尾结点的next指针是否为空。
单链表：不带头单向不循环
双向链表：带头双向循环
