CLRS10.2-7练习

要求:

Give a Θ(n)-time nonrecursive procedure that reverses a singly linked list of n
elements. The procedure should use no more than constant storage beyond that
needed for the list itself.

中心思想是同时取出并保存链表中的连续三个元素(previous, current, after),并翻转前两个,然后每次将这三个指针依次向后移一位并重复翻转前两个,直至结束

伪代码:

LIST-REVERSE(L)

1 previous = L.head

2 if previous.next ≠ NIL

3  current = previous.next

4 else return

5 if current.next ≠ NIL

6  after = current.next

7 else L.head = current

8  current.next = previous; previous.next = NIL

9  return

10 current.next = previous; previous.next = NIL

11 while after.next ≠ NIL

12  previous = current

13  current = after

14  after = after.next

15  current.next = previous

16 after.next = current

17 L.head = after

18 return

存储空间开销-三个指针

原文地址:https://www.cnblogs.com/dgzhangning/p/7655915.html