Skip to content

Latest commit

 

History

History
34 lines (21 loc) · 1.36 KB

README.md

File metadata and controls

34 lines (21 loc) · 1.36 KB

Solution

Approach #1(迭代)

每次循环将curr.next修改为前一节点

因为需要将当前节点的next节点修改为前一节点,所以需要用一个指针prev记录前一节点。同时,由于修改了当前节点的next节点后,无法访问原来的next节点,因此需要一个指针next,在修改前记录原来的next节点

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

Approach #2(递归)

n(1) -> n(2) -> ... -> n(k) -> n(k+1) <- ... <- n(m)

在m个节点的链表中,对于每次递归处理的节点k,假设节点k之后的节点已经处理完(逆序)。对于节点k,只需修改其next成员,以及节点(k+1)的next成员

n(k)->next->next = n(k);
n(k)->next = NULL;

函数返回逆序后链表的头结点,因此对于n(m),直接返回n(m)

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)(每次递归函数栈帧都会创建1个局部指针保存逆序后的链表头结点)

注:不能假设对于每次递归处理的节点k,前k-1个节点已经逆序。因为节点k无法访问到前一节点,因此无法将k节点逆序,因此对于节点k+1,前k个节点无法逆序。也不能假设前k个节点已经逆序,因为如果前k个节点已经逆序,对于节点k,将k+1节点逆序,当处理k+1节点时,无法访问到k+2节点