单链表的逆置算法

作者: admin 分类: 未分类 发布时间: 2018-11-20 00:13

如何实现简单快速的实现单链表的逆置。(要求时空复杂度尽量低。)

最简单的一个思路是遍历一遍链表,存储到临时数组,然后利用这个临时数组重新建立一个新的链表。这样的话时间复杂度暂且认为是O(n),但是却需要O(n)的空间复杂度。下面说另外一种不需要辅助空间,并且时间复杂度也是O(n)的算法,该算法被称为头插法,即便利链表的每个元素时,把元素直接插入到链表的表头,这样就完成了链表的逆置。

//算法功能:完成头结点为head的链表的逆转,链表中的第一个节点是head->next。
node * reverse(node *head)

{

  if(head == NULL)

  {

    return NULL;  

  }

  node *temp = head->next;

  while(temp != NULL)

  {

     temp -> next = head;

    head  = temp;

    temp = temp-> next;

  }

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注