c++单链表逆置内存结构分析

新建一个单链表l内存结构如图:

可见是带有3个node的list.

现在分析其逆置过程的内存结构变化,c++源码如下:

void reverse_4(list& l) {
	node* a = l.next;
	node* b = NULL;
	while (a->next != NULL)
	{
		b = a->next;		//-->①
		a->next = b->next;	//-->②
		b->next = l.next;	//-->③
		l.next = b;			//-->④
	}
}

程序执行到①时的内存结构如图:

可见此时l的结构无变化,a截获了l.next,b截获了a->next,此时三者的结构为: a=0-1-2-N,b=1-2-N,l-0-1-2-N.

当程序执行到②时的内存结构如图:

可见将a->next与b->next嫁接的时候,l的第二个node也被影响,此时三者的结构变为: a=0-2-N,b=1-2-N,l-0-2-N.

当程序执行到③时的内存结构如图:

当程序执行到④时的内存结构如图:

可见这时候l.next=b=1-0-2-N.即一次循环得到的链表头节点结构只完成了前两个节点的逆置,且a->next->next=NULL,需要再循环一次完成全部逆置.

接下来第二次循环:

①:a=0-2-N,b=2-N,l.next=b=1-0-2-N     

②:a=0-N,b=2-N,l-1-0-N                        //ab嫁接过程,l再次重新链接

③:a=0-N,b=2-1-0-N,l-1-0-N                 //已经完成三个节点的逆置

④:a=0-N,l.next=b=2-1-0-N                  //返回l的逆置,第二次循环结束