单链表（不带头结点）各种操作

主函数中根据需求直接调用就可。

单链表结构定义

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(NULL) {} ListNode(int x) : val(x), next(NULL) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };

各个子函数功能及说明

ListNode *createByTail();//创建链表 void displayLink(ListNode *head);//遍历单链表 ListNode* sortList(ListNode* head);//在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 void reorderList(ListNode* head);//给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… ListNode* rotateRight(ListNode* head, int k)//给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 vector<ListNode*> splitListToParts(ListNode* root, int k)//给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。返回一个符合上述规则的链表的列表。 ListNode* reverseKGroup(ListNode* head, int k)//给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 ListNode* oddEvenList(ListNode* head);//把所有的奇数节点和偶数节点分别排在一起 ListNode* swapPairs(ListNode* head);//给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换

子函数具体实现代码

//尾插法创建单链表 ListNode *createByTail() { ListNode *head; ListNode *p1,*p2; int n=0,num; int len; cin>>len;//单链表元素个数 head=NULL; while(n<len && cin>>num)//输各个元素的值 { p1=new ListNode(num); n=n+1; if(n==1)//处理第一个元素 head=p1; else p2->next=p1; p2=p1; } return head； } //遍历，这是最基础的部分 void displayLink(ListNode *head) { ListNode *p; p=head; cout<<"head-->"; while(p!= NULL) { cout<<p->val<<"-->"; p=p->next; } cout<<"tail\n"; } //从小到大进行排序 思路使用vector容器保存各个结点，利用algorithm头文件里面的sort方法直接排序 //如果是从大到小进行排列加上下面的函数 bool cmp(int a,int b){ return a>b; } //sort函数变成 sort(v.begin(), v.end(),cmp); ListNode* sortList(ListNode* head){ if(head==NULL || head->next==NULL) return head; vector<int> v; while(head){ v.push_back(head->val); head = head->next; } sort(v.begin(), v.end()); //利用容器里面的结点直接连到一起就可 ListNode* L = new ListNode(v[0]); ListNode *tail = L,*s; for(int i=1;i<v.size();i++){ s = new ListNode(v[i]); tail->next=s; tail = s; } return L; } //思路，利用栈 void reorderList(ListNode* head) { //填充本函数完成功能 stack<ListNode *> s; int i,len; ListNode *p=head,*tail,*temp; //将所有结点入栈 while(p){ s.push(p); p=p->next; } p=head; len=s.size(); if(len<=2) return ; //将栈中一半的元素弹出，边弹出边插入原链表中 for(i=0;i<len/2;i++){ ListNode *x=p->next; temp=s.top(); temp->next=p->next; s.pop(); p->next=temp; p=x; } p->next=NULL; } //将链表每个节点向右移动 k 个位置,相当于尾节点p移动 len-（k%len）次，此时下一个结点即为移动后链表的头结点 ListNode* rotateRight(ListNode* head, int k) { if(head==NULL || head->next==NULL) return head; int len = 1; ListNode *p = head; while(p->next){ len++; p=p->next; } p->next = head;//p为尾结点，做成循环单链表 if(k%=len){ for(int i=0; i<len-k; ++i) p = p->next; } ListNode *res = p->next;//移动后 链表的头结点位置 p->next = NULL;//移动后 链表的尾结点位置，next域置为NULL return res; } //这个题回归原始，变成数学题来做，思考假若有10个结点，分成k=4段，应该怎么做 // 首先 n=10/4; 求得的n为平均每段的长度 。m=10%4=2，也就意味着这两个结点要分配到这四段中某段，由于题中明确表示每段的长度之差不能超过1，显然每段从前往后把这‘2’给一个一个消耗掉，那么每段的长度就是3, 3，2 ，2， 那么接下来的问题就是按照刚才计算出来的每段长度分别串联成一小段，并把每段的头结点存储在vector 结果集中即可 vector<ListNode*> splitListToParts(ListNode* root, int k) { int i=0,n; ListNode *p=root,*temp; vector<ListNode *> vec; //计算链表长度 while(p){ i++; p=p->next; } //考虑特殊情况 if(i<=k){ p=root; while(p){ ListNode *temp=p->next; p->next=NULL; vec.push_back(p); p=temp; } n=k-i; while(n--){ vec.push_back(NULL); } return vec; } n=i/k; int m=i%k; p=root; while(k--){ vec.push_back(p); i=1; while(p&&i%n!=0){ p=p->next; i++; } if(m){ p=p->next;//再往后多一位，消耗掉m m--; } temp=p->next; p->next=NULL; p=temp; } return vec； } //这个题就是综合了上题的思想以及逆序，这两种操作都会这道题就很easy了，分段--》逆序 ListNode* reverseKGroup(ListNode* head, int k) { //填充本函数完成功能 if(head==NULL ) return NULL ; ListNode *L=new ListNode; L->next=head; ListNode *p=L->next,*q,*pre; int len=0,m; while(p){ len++; p=p->next; } int n=len/k; p=L->next;q=L; while(n--){ m=0; pre=p; while(m!=k && p){ m++; ListNode *temp=p->next; p->next=q->next; q->next=p; p=temp; } q=pre; } q->next=p; return L->next; } //原地工作 ListNode* oddEvenList(ListNode* head) { ListNode *p=head,*p1,*p2; //创建临头结点 ListNode L1(0);//连接奇数位置结点 ListNode L2(0); //连接偶数数位置结点 p1=&L1;p2=&L2; while(p){ p1->next=p; p1=p; p=p->next; if(p){ p2->next=p; p2=p; p=p->next; } } p1->next=L2.next;//奇数链表的尾结点的next域指向偶数结点链表的第一个结点 p2->next=NULL; return L1.next; } //画个示意图就很好理解 ListNode* swapPairs(ListNode* head) { if(head==NULL || head->next==NULL)//如果链表中为空或者仅有一个元素，返回原链表 return head; ListNode *res=new ListNode; res->next=NULL; ListNode *p,*q,*tail; tail=res; p=head; while(p&&p->next){//一定要有p->next q=p->next; tail->next=q; tail=q; q=q->next; tail->next=p; tail=p; p=q; } if(p){ tail->next=p; tail=p; } tail->next=NULL; return res->next; }