数据结构代码集训day13（适合考研、自学、期末和专升本）
题目来自：B站up白话拆解数据结构
今日题目如下：
设线性表 L= ( a1，a2，a3…，an-2，an-1，an) 采用带头结点的单链表保存，链表中结点定义如下：
typedef struct node {
int data ；
struct node* next ；
} Node ；
请设计一个空间复杂度为 O ( 1 ) 且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L’= ( a1，an，a2，an-1，a3，an-2…) 。
要求：
( 1 ) 给出算法的基本设计思想
( 2 ) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
( 3 ) 说明你所设计的算法的时间复杂度。
这个题目比较综合，运用了前面的快慢指针，链表反转等思想。
首先分析题目，重新排列后的表把后半部分反转了，然后依次插入进去前半部分表里了。
所以我们要做三件事情：
（1）找到前半部分表和后半部分的分界点，采用快慢指针
Lnode *slow = L, *fast = L;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
- 如果链表长度为单数，则
slow最终指向中间节点。 - 如果链表长度为偶数，
slow会指向前半部分的最后一个节点。
（2）反转链表后半部分，就是链表逆置的代码
Linklist list_reverstbyhead(Linklist &L){
Lnode *p, *r;
p = L->next;
L->next = NULL;
while(p){
r = p->next;
p->next = L->next;
L->next = p;
p = r;
}
return L;
}
然后把slow当这里面的L传进去就行了。
（3）重新排列，断开前后部分，将后面的一个个插进去就行了。
单数情况：
Lnode *p = slow->next; // 后部分第一个结点
Lnode *q = p->next; // 后部分第一个结点的下一个
Lnode *t = L->next; // 前部分第一个结点
Lnode *n; // 在里面赋值和外面赋值没什么差别
slow->next=NULL; //分隔开
while (t!=slow) { //单数偶数判断条件不一样
n = t->next;
q = p->next;
t->next = p;
p->next = n;
t = n;
p = q;
}
偶数情况：
Lnode *p = slow->next;
Lnode *q = p->next;
Lnode *t = L->next;
Lnode *n;
slow->next=NULL;
while (t) {
n = t->next;
q = p->next;
t->next = p;
p->next = n;
t = n;
p = q;
}
实践一下：
单数情况如下
偶数情况如下
完整代码如下：
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
// 单链表结构体定义
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L){
Lnode *s;
int x;
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
cin >> x;
while(x!=9999){
s = (Lnode*)malloc(sizeof(Lnode));
s->data=x;
s->next=NULL;
r->next = s;
r=r->next;
cin >> x;
}
return L;
}
// 将带头结点的单链表{a1.a2....an}重新排列成{a1，an，a2，an-1...},空间复杂度要求O（1）
Linklist list_reverstbyhead(Linklist &L){
Lnode *p, *r;
p = L->next;
L->next = NULL;
while(p){
r = p->next;
p->next = L->next;
L->next = p;
p = r;
}
return L;
}
Linklist func(Linklist &L){
if (L == nullptr || L->next == nullptr) return L;
Lnode *slow = L, *fast = L;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
list_reverstbyhead(slow);
Lnode *p = slow->next;
Lnode *q = p->next;
Lnode *t = L->next;
Lnode *n;
slow->next=NULL;
while (t) {
n = t->next;
q = p->next;
t->next = p;
p->next = n;
t = n;
p = q;
}
return L;
}
int main(){
Linklist L;
list_insertbytail(L);
Lnode *p = L->next;
printf("origin list:");
while (p != NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
func(L);
printf("new list:");
Lnode *q = L->next;
while (q != NULL) {
printf("%d-> ",q->data);
q = q->next;
}
printf("NULL\n");
return 0;
}