1.移除链表元素
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。
思路: 创建新链表,找值不为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;//遍历原链表ListNode*pcur=head;while(pcur){//找值不为val的节点,尾插到新链表中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;
}
2.反转链表
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。
思路:创建三个指针,完成原链表的翻转。
/*** 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;}//创建3个指针ListNode*n1,*n2,*n3;n1=NULL;n2=head;n3=n2->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)//n3可能已经走到空了n3=n3->next;}return n1;
}
3.链表的中间节点
给你单链表的头结点
head
,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
思路:使用快慢指针,慢指针每次走一步,快指针每次走两步。
/*** 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=slow->next;fast=fast->next->next;}//此时slow刚好指向中间节点return slow;
}
while(fast&&fast->next) 语句可以写成 while(fast->next&&fast)吗?
不可以。若链表中有偶数个节点,fast最后会直接走到空,fast->next操作对空指针进行解引用,会报错!
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) {//判空 list1为空 list2为空 list和list2都为空if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode*l1=list1;ListNode*l2=list2;//创建的新链表ListNode*newHead=NULL;ListNode*newTail=NULL;while(l1&&l2){if(l1->val<l2->val){//l1拿下来尾插if(newHead==NULL){newHead=newTail=l1;}else{newTail->next=l1;newTail=newTail->next;}l1=l1->next;}else{//l2拿下来尾插if(newHead==NULL){newHead=newTail=l2;}else{newTail->next=l2;newTail=newTail->next;}l2=l2->next;}}//跳出循环有两种情况:一.l1走到空了 二.l2走到空了if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}return newHead;
}
仔细观察,上面代码存在重复,重复操作判断链表是否为空,怎么解决这个问题呢?
让新链表不为空。使用malloc函数给 newHead 和 newTail 指针申请一块空间,它们不再是空指针,此时链表不为空,头尾指针都指向了一个有效的地址。如下图,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) {//判空 list1为空 list2为空 list和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){//l1拿下来尾插newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{//l2拿下来尾插newTail->next=l2;newTail=newTail->next;l2=l2->next;}}//跳出循环有两种情况:1.l1走到空了 2.l2走到空了if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}//动态申请的空间手动释放掉ListNode* ret=newHead->next; //newHead的下一个节点保存下来free(newHead);newHead=NULL;return ret;
}
5.循环链表经典应用
——环形链表的约瑟夫问题
著名的Josephus问题
据说著名犹太 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与 Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个人重新报数,直到所有人都自杀身亡为止。 然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己自排在第16个与第31个位置,于是逃过了这场死亡游戏。
题目描述
思路:
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 ) {// 根据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;
}
6.分割链表
题目描述
思路:
/*** 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;}//修改大链表的尾节点的next指针的指向greaterTail->next=NULL; //小链表的尾节点和大链表的第一个有效节点首尾相连lessTail->next=greaterHead->next;ListNode*ret=lessHead->next;free(lessHead);free(greaterHead);lessHead=greaterHead=NULL;return ret;
}