仿真链表k个一组反转链表

PAT乙级k个一组反转链表有两种方式,第一种是用仿真链表k个一组反转链表,第二个是直接用链表,下面用仿真链表来实现,最后附上真实链表的代码。

思路:先学会反转整个链表,然后反转指定节点之间的链表,例如链表 a - b - c ,只反转成b - a - c,这样递归下去就能实现反转整个链表咯

链表结构体

1
2
3
4
struct node{
int next;
int data;
}

反转指定节点段

//反转节点a到b之间的节点,返回新头节点,此时b成为独立的链表

1
2
3
4
5
6
7
8
9
10
11
int Reverse(int a,int b,node link[]){
int pre, cur, nxt;
pre=-1; cur=a; nxt=a;
while (cur != b) {
nxt=link[nxt].next; //下一个节点移动到当前的下一个
link[cur].next = pre; //当前节点等于前一个
pre = cur;
cur = nxt;
}
return pre;
}

K个一组反转

1
2
3
4
5
6
7
8
9
10
11
12
13
int reverseKGroup(int head,int k,node link[]) {
if(head==-1) return -1;
int a, b;
a = head;
b = head;
for (int i = 0; i < k; i++) {
if (b == -1) return head;
b = link[b].next; //找到k的下一个节点
}
int newHead = Reverse(a, b,link);
link[a].next = reverseKGroup(b,k,link); //递归并连接所有节点
return newHead;
}