【数据结构】单链表的应用

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;
}