目录

1、反转链表

2、链表内指定区间反转

3、链表中每K个节点翻转

不太会用网上的那种刷题软件自带的测试器，时间复杂度超没超不清楚。

1、反转链表

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度 O(n) 。

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

#include <stdio.h>
#include <stdlib.h>int flag = 1;typedef struct node{int data;struct node *next;
}list,*link;
void pp(int num)
{if(flag == 1){switch(num){case 0:printf("\\nError%d: Failed to malloc!\\n",num);break;case 10086:printf("\\nll is NULL\\n");default:printf("\\nError: unknown error!\\n");}}
}link create()
{link ll;if((ll = (link)malloc(sizeof(link))) == NULL){pp(0);return NULL;}ll->data = 0;ll->next = NULL;return ll;
}void l_free(link ll)
{link p;while(ll){p = ll;ll = ll->next;printf("free:%d\\n",p->data);p->next = NULL;free(p);p = NULL;}
}int l_show(link ll)
{if(ll == NULL){pp(10086);return -1;}link p;p = ll;printf("ll = ");if(p->next == NULL){printf("This is only head!\\n");return 0;}p = p->next;while(p){printf("%d ",p->data);p = p->next;}puts("");return 0;
}int insert_head(link ll, int a)
{link p;p = (link)malloc(sizeof(link));if(p == NULL){pp(0);return -1;}p -> data = a;p -> next = ll -> next;ll -> next = p;return 0;
}int insert_tail(link ll, int a)
{link p,q; p = (link)malloc(sizeof(link));if(p == NULL){pp(0);return -1;}p -> next = NULL;p -> data = a;q = ll;while(q->next);q -> next = p;return 0;
}link get_tail(link ll)
{if(ll == NULL){pp(10086);return NULL;}link p;p = ll;while(p -> next != NULL);return p;
}int l_in(link ll)
{link p,q,t;if(ll == NULL){pp(10086);return -1;}printf("input:\\n");while(1){printf(">>>");int i;scanf("%d",&i);if(i == -1)break;insert_head(ll,i);}l_show(ll);
#if 0t = ll->next;while(1){q = ll;p = get_tail(ll);if(t == p){break;}p -> next = q -> next;q -> next = p;}l_show(ll);
#endifreturn 0;
}int main()
{link ll;ll = create();l_in(ll);l_free(ll);return 0;
}

 喵喵的写了一天，技能严重退化。

2、链表内指定区间反转

int l_m_n(link ll)
{	int a[1000];int min,max;int i = 0;printf("input<<<");while(1){scanf("%d",&a[i]);if(a[i] == -1)break;i++;}printf("input min:");scanf("%d",&min);printf("input max:");scanf("%d",&max);i = i-1;for(;i >= 0;i--){
#if 1if(i <= (max-2) && i >= (min-1)){insert_head(ll -> next,a[i]);}else{insert_head(ll,a[i]);}
#elseinsert_head(ll,a[i]);
#endif}l_show(ll);return 0;
}

 规范一下，把函数都放在link.c,声明都放在link.h主函数是test.c

3、链表中每K个节点翻转

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>typedef struct ListNode ListNode;struct ListNode {int val;struct ListNode *next;
};void ListPush(ListNode **head, int val)
{ListNode *pre = NULL;ListNode *cur = (*head);if(cur == NULL){*head = (ListNode *)malloc(sizeof(ListNode));(*head)->val = val;(*head)->next = NULL;return;}while(cur){pre = cur;cur = cur->next;}cur = (ListNode *)malloc(sizeof(ListNode));pre->next = cur;cur->val = val;cur->next = NULL;return;
}void ListFree(ListNode **head)
{ListNode *next = NULL;ListNode *cur = (*head);while(cur){next = cur->next;free(cur);cur = next;}*head = NULL;
}void ListPrint(ListNode *head)
{ListNode *cur = head;while(cur){printf("%d ", cur->val);cur = cur->next;}printf("\\n");
}struct ListNode *reverseKGroup(struct ListNode *head, int k)
{struct ListNode *pre = NULL;struct ListNode *cur = head;struct ListNode *next = NULL;struct ListNode *t[2] = {NULL, NULL};int len = 0;int u = 0;int i;if(head == NULL){return head;}if(k == 1){return head;}while(cur){cur = cur->next;len++;}u = len / k;if(u == 0){return head;}pre = NULL;cur = head;for(i=0; i<k; i++){next = cur->next;cur->next = pre;pre = cur;cur = next;}head->next = cur;t[0] = pre;pre = head;head = t[0];t[0] = pre;u--;while(u){for(i=0; i<k; i++){next = cur->next;cur->next = pre;pre = cur;cur = next;}t[1] = t[0]->next;if(t[0]->next){t[0]->next->next = cur;}t[0]->next = pre;pre = t[1];t[0] = pre;u--;}return head;
}int main()
{ListNode *head = NULL;ListPush(&head, 1);ListPush(&head, 2);ListPush(&head, 3);ListPush(&head, 4);ListPush(&head, 5);ListPush(&head, 6);ListPrint(head);head = reverseKGroup(head, 3);ListPrint(head);ListFree(&head);return 0;
}

还得是大佬呀。这个程序是在网上找的，写了一上午没写出来心态崩了。