习题选讲-Reversing Linked List.pdf

《习题选讲-Reversing Linked List.pdf》由会员分享，可在线阅读，更多相关《习题选讲-Reversing Linked List.pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性结构之 习题选讲线性结构之 习题选讲 Reversing Linked List 什么是抽象的链表什么是抽象的链表 有块地方存数据有块地方存数据 有块地方存指针有块地方存指针 下一个结点的地址下一个结点的地址 Sample Input: 00100 6 4 00000 4 99999 00100 1 12309 68237 6 -1 33218 3 00000 99999 5 68237 12309 2 33218 00000 4 99999 00100 1 12309 12309 2 33218 33218 3 00000 68237 6 NULL 99999 5 68237 12345

2、6 单链表的逆转单链表的逆转 123456 123456 newold Ptr Reverse( Ptr head, int K ) cnt = 1; new = head-next; old = new-next; while ( cnt next; old-next = new; new = old; old = tmp; cnt+; head-next-next = old; return new; 取巧：用顺序表存储，取巧：用顺序表存储， 先排序，再直接逆序输先排序，再直接逆序输 出。出。 在在“内存内存”里多加几里多加几 个没用的结点，让个没用的结点，让 你偷懒！你偷懒！ 测试数据测试数据 有尾巴不反转有尾巴不反转 地址取到上下界地址取到上下界 正好全反转正好全反转 K=N全反转全反转 K=1不用反转不用反转 最大（最后剩最大（最后剩K-1不反转）、最小不反转）、最小N 有多余结点有多余结点 边界测试边界测试