使用以下代码以不同的方式反转链表的时间复杂度是多少?

Question

给定一个链表$link 1，元素为 (a->b->c->d->e->f->g->h->i->j)，我们需要反转链表，前提是反转将以如下方式完成 -

反转第一要素 (a)

反转接下来的 2 个元素 (a->c->b)

反转接下来的 3 个元素 (a->c->b->f->e->d)

反转接下来的 4 个元素 (a->c->b->f->e->d->j->i->h->g)

....

....

我在PHP中创建了以下代码来解决此问题

我需要的东西——

1. 我需要在下面计算反向链接列表函数的时间复杂度。

2. 需要知道我们是否可以优化反向链接列表函数来降低时间复杂度。

-

class ListNode
{
public $data;
public $next;
function __construct($data)
{
$this->data = $data;
$this->next = NULL;
}
function read_node()
{
return $this->data;
}
}
class LinkList
{
private $first_node;
private $last_node;
private $count;
function __construct()
{
$this->first_node = NULL;
$this->last_node = NULL;
$this->count = 0;
}
function size()
{
return $this->count;
}
public function read_list()
{
$listData = array();
$current = $this->first_node;
while($current != NULL)
{
echo $current->read_node().' ';
$current = $current->next;
}
}
public function reverse_list()
{
if(($this->first_node != NULL)&&($this->first_node->next != NULL))
{
$current = $this->first_node;
$new = NULL;
while ($current != NULL)
{
$temp = $current->next;
$current->next = $new;
$new = $current;
$current = $temp;
}
$this->first_node = $new;
}
}

public function read_node($position)
{
if($position <= $this->count)
{
$current = $this->first_node;
$pos = 1;
while($pos != $position)
{
if($current->next == NULL)
return null;
else
$current = $current->next;
$pos++;
}
return $current->data;
}
else
return NULL;
}
public function insert($data)
{
$new_node = new ListNode($data);
if($this->first_node != NULL)
{
$this->last_node->next = $new_node;
$new_node->next = NULL;
$this->last_node = &$new_node;
$this->count++;
}
else
{
$new_node->next = $this->first_node;
$this->first_node = &$new_node;
if($this->last_node == NULL)
$this->last_node = &$new_node;
$this->count++;
}
}
}

//Create linked list
$link1 = new LinkList();
//Insert elements
$link1->insert('a');
$link1->insert('b');
$link1->insert('c');
$link1->insert('d');
$link1->insert('e'); 
$link1->insert('f'); 
$link1->insert('g'); 
$link1->insert('h');
$link1->insert('i'); 
$link1->insert('j'); 
echo "<b>Input :</b><br>";       
$link1->read_list();

//function to reverse linked list in specified manner
function reverseLinkedList(&$link1)
{
$size= $link1->size();
if($size>2)
{
$link2=new LinkList();
$link2->insert($link1->read_node(1));
$elements_covered=1;
//reverse
$rev_size=2;
while($elements_covered<$size)
{
$start=$elements_covered+1;
$temp_link = new LinkList();
$temp_link->insert($link1->read_node($start));
for($i=1;$i<$rev_size;$i++)
{
$temp_link->insert($link1->read_node(++$start));
}
$temp_link->reverse_list();
$temp_size=$temp_link->size();
$link2_size=$link2->size();
for($i=1;$i<=$temp_size;$i++)
{
$link2->insert($temp_link->read_node($i));
++$elements_covered;
++$link2_size;
}
++$rev_size;
}
///reverse 
//Flip the linkedlist
$link1=$link2;
}    
}
///function to reverse linked list in specified manner
//Reverse current linked list $link1
reverseLinkedList($link1);
echo "<br><br><b>Output :</b><br>";       
$link1->read_list();

Answer 1

这是O(n)...只需一次遍历。

其次，这里没有必要用语言标记它。

我在这里提供了一个伪代码供您参考：

current => head_ref
prev    => NULL;
current => head_ref;
next    => null;
while (current != NULL)
{
next  = current->next;  
current->next = prev;   
prev = current;
current = next;
}
*head_ref = prev;