数据结构 – 反转链表

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

头结点->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。

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