数据结构 – 反转链表

假如我们已经构造了如下链表:

头结点->6->5->4->3->2->1->null

现在要求反转链表,使其变成:

头结点->1->2->3->4->5->6->null

思路分析:既然是反过来,那么就从反过来后的第一个元素入手,即null,让第一个结点的next先指向null,类似: 6->null这个结构,继续这个思路,那下一步就是让5指向刚刚这个结构,依次类推,知道最后一个1指向2->3->4->5->6->null

代码:

// 2. 链表反转: 假设有链表6->5->4->3->2->1,反转链表成为1->2->3->4->5->6
function reverse(LineStruct $linelist) {
	// 第一个结点
	$pre = null;
	$leftNodes = $linelist->next;	
	while($leftNodes) {
		① $temp = $leftNodes->next;
		② $leftNodes->next = $pre;
		③ $pre = $leftNodes;
		④ $leftNodes = $temp;
	}
	$headNode = new LineStruct('',$pre);
	return $headNode;
}

先从第一遍开始分析,$leftNodes为6->5->4->3->2->1->null,之所以叫leftNodes,抽象表示剩下的结点,① 我们先用$temp保存6的下一个结点,即5->4->3->2->1->null,② 然后让6指向预先定义的pre,第一个当然是null,这个pre后面会改变。得到的结构是6->null,③ 接着我们用pre来保存这个结构,最后也是最重要的一部步,④将$leftNodes用$temp的值替换,那么下次循环就是从5这个结点开始了,先保存剩下的结点,,即4->3->2->1->null,然后5会先指向刚刚的pre,即6->null,变成5->6->null,这个结构一会再保存为pre,然后再讲$leftNodes置为$temp,直到最后一个$leftNodes = null,跳出循环,这时候的$pre就是1->2->3->4->5->6->null。

所以整个思路里最重要的就是保存当前结点的下一个结点,即保存剩下的结点。

 

发表评论

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