线性结构之习题选讲-ReversingLinkedList

2024-10-19 23:51:39

目录

一、什么是抽象的链表
二、单链表的逆转
三、测试数据
- 3.1 边界测试

更新、更全的《数据结构与算法》的更新网站，更有python、go、人工智能教学等着你：https://www.cnblogs.com/nickchen121/p/11407287.html

一、什么是抽象的链表

有块地方存储数据
有块地方存储指针——下一个结点的地址

二、单链表的逆转

/* c语言实现 */

Ptr Reverse(Ptr head, int K)

{

  cnt = 1;

  new = head->next;

  old = new->next;

  while (cnt < K) {

    tmp = old->next;

    old->next = new;

    new = old; old = tmp;

    cnt++;

  }

  head->next->next = old;

  return new;

}

取巧：用顺序表存储，先排序，再直接逆序输出。

对上述取巧的解决方案：在内存里多加几个没用的结点。

三、测试数据

在pta测试中，这道题的测试数据主要关心一下几点：

有尾巴不反转
有多余结点

3.1 边界测试

地址取到上下界
正好全反转
K=N全反转
K=1不用反转
最大（最后剩K-1不反转）、最小N

最新文章

热门文章