链表题目练习及讲解（上）：https://developer.aliyun.com/article/1624369
4.环形链表的约瑟夫问题
当m=2时，模拟的过程
一直循环下去...
最后3指向3
本题借助循环链表思路，先创建带环链表，创建从1到n节点的链表（通过尾插），在通过双指针的移动寻找留下的编号。
从第一个节点报数，需要知道前节点，刚开始定义prev指向尾节点，pcur=prev->next;
从count=1开始报数，到指定m之前，指针移动，prev=pcur,pcur=prev->next,count++,到m时，先让prev->next=pcur->next,在销毁当前节点pcur,再让野指针pcur=prev->next;count变为1，一直循环下去，直到pcur->next指向自己时，跳出循环，返回该节点的值。
struct ListNode{ int val; struct ListNode*next; }; 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*creatcircle(int n){ ListNode*head=buynode(1); ListNode*tail=head; for(int i=2;i<=n;i++){ tail->next=buynode(i); tail=tail->next; } //首尾相连 tail->next=head; return tail; } int ysf(int n, int m ) { //创建环形链表 ListNode*prev=creatcircle(n); ListNode*pcur=prev->next; int count=1; while(pcur->next!=pcur){ if(count==m){ prev->next=pcur->next; free(pcur); pcur=prev->next; count=1; } else { prev=pcur; pcur=pcur->next; count++; } } return pcur->val; }
5.分割链表
思路:创建两个新的链表，一个大链表存储比特定值大的节点，小链表存储比特定值小的节点，最后将两个链表连接起来，因此我们需要定义四个节点，两头两尾，然后采用尾插的方式相应节点插入到大小链表中。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x){ ListNode*lesshead,*lesstail,*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; } greatertail->next=NULL; //小链表与大链表连接 lesstail->next=greaterhead->next; ListNode*ret=lesshead->next; free(lesshead); free(greaterhead); lesshead=greaterhead=NULL; return ret; }
6.相交链表
https://leetcode.cn/problems/intersection-of-two-linked-lists/
需要判断链表是否相交(通过判断尾指针，注意需要用地址判断，用值判断有缺陷，可能两个链表的节点值相等，但是节点不相交)，若相交，找出第一个交点。
一般我们会想到，让A链表的节点依次与B链表节点比较， A链表的某个节点与B链表某个节点相等，这个节点就是交点，该时间复杂度为O(N^2)
/* struct ListNode { int val; struct ListNode *next; }; */ typedef struct ListNode LN; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { LN*cur1=headA,*cur2=headB; int lenA=1,lenB=1; while(cur1){ cur1=cur1->next; lenA++; } while(cur2){ cur2=cur2->next; lenB++; } //尾节点不相同就没有相交 if(cur1!=cur2){ return NULL; } //假设法,先假设LIstA是长链表。 int gap=abs(lenA-lenB); LN* longlist = headA; LN* shortlist = headB; if(lenA<lenB){ longlist=headB; shortlist=headA; } //同时移动时，让长链表与短链表的相对起始位置相同。 while(gap--){ longlist=longlist->next; } while(longlist!=shortlist){ longlist=longlist->next; shortlist=shortlist->next; } return longlist; }
