数据结构与算法-单链表的应用

一. 移除链表元素

函数实现+解析：

/*** 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)//遍历{if(pcur->val!=val)//不是val的节点{if(newHead==NULL)//空链表，也就是刚开始王空链表放节点{newHead=newTail=pcur;}else//不是空链表，往单链表中尾插节点{newTail->next=pcur;newTail=pcur;}}pcur=pcur->next;//遍历，一次过后往后移}if(newTail)//判断是否为空，为空就不能进行解引用newTail->next=NULL;//因为尾节点既有数据也有指向下一个节点的指针，所以如果不将其NULL化，那么原先单链表的尾节点还是不会变。return newHead;
}

二. 反转链表

思路：

运用三个指针，n1，n2，n3，n1是空指针，n2初始化为头节点地址，n3初始化为n2的下一个节点，然后将n2的next指向n1，n2再往后挪到下一个节点，也就是n3指向的节点，然后n3再等于n2的next指向的节点，以此类推就可以使得单链表反转，最后循环判断条件的n2是否为空指针。

函数实现：

/*** 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=NULL;ListNode*n2=head;ListNode*n3=n2->next;//正式开始while(n2){n2->next=n1;n1=n2;n2=n3;if(n3)n3=n2->next;}return n1;
}

三. 寻找单链表中间节点

思路：

1.遍历一边，用count++计数，然后进行半遍历找到中间节点，还要区分奇偶数的条件

2.快慢指针，slow和fast进行一次遍历就好。

函数实现：（思路2）

//寻找单链表的中间节点
//如果是偶数，则会返回第二个一样的节点
//这是非常好用的快慢指针的运用
/*** 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;}return slow;
}

四. 合并两个有序链表

函数思路：

创建一个空链表，两个单链表节点进行比较，谁小谁就放进空链表中然后继续往后比较直到结束。

函数实现：

/*** 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=NULL;ListNode*newTail=NULL;while(l1&&l2){if(l1->val<l2->val){if(newHead==NULL){newHead=newTail=l1;}else{newTail->next=l1;newTail=newTail->next;}l1=l1->next;}else{if(newHead==NULL){newHead=newTail=l2;}else{newTail->next=l2;newTail=newTail->next;}l2=l2->next;}}if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}return newHead;}

函数优化：

（无需重复判断新创链表是否为空，不再创建空链表，直接malloc一块空间作为节点进行使用）

/*** 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->next;}else{newTail->next=l2;newTail=newTail->next;l2=l2->next;}}if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}ListNode*ret=newHead->next;free(newHead);newHead=NULL;return ret;
}

这里实际使用了带头链表，创建的头节点可以称之为哨兵位

五. 环形链表的约瑟夫问题

函数实现：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param n int整型 * @param m int整型 * @return int整型*/typedef struct ListNode ListNode;//创建节点ListNode*buyNode(int x){ListNode*newHead=(ListNode*)malloc(sizeof(ListNode));if(newHead==NULL){exit(1);}newHead->val=x;newHead->next=NULL;return newHead;}
//创建循环链表
ListNode*circle(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=circle(n);ListNode*pcur=prev->next;int count = 1;while(pcur->next!=pcur){if(count!=m){prev=pcur;pcur=pcur->next;count++;}else{prev->next=pcur->next;free(pcur);pcur=prev->next;count=1;}}return pcur->val;
}