【数据结构】单链表逆置：头插法图解

利用头插法能重新建立带头节点的新链表

下面简单介绍一下，算法思想结合图示看

算法思想：逆置链表初始为空，表中节点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。

LNode *Inverse(LNode *L)
{
	LNode *p, *q;
	p = L->next;
	L->next = NULL;
	while (p != NULL)
	{
		q = p;
		p = p->next;

		q->next = L->next;
		L->next = q;
	}
	return L;
}

接下来，进行图解：

刚开始是这样

’循环前的操作

进入循环，分别用q和p记录第一个和第二个节点

 进入第二轮循环，这是发生重大变化的关键时期

 这张图调整一下

 直到链表为空

这篇文章已经一年半了，还是源源不断有不同的评论，去探讨相关的问题，其实图解不一定清晰。下面用更简明的方式给大家说一下什么情况。

这里采用Java的写法，C一定也能看懂。

我首先创建三个节点，一个是当前节点cur、一个是cur上一个节点pre。另外就是tmp。

每次循环，我用tmp记录cur下一个节点，接着将cur的next指针指向上一个节点pre。这个时候就完成了一次反转操作。

接着将pre和cur的记录往后移动一次，重复上面的操作。

直至达到链表结尾。

class Solution {
	public ListNode reverseList(ListNode head) {
		//申请节点，pre和 cur，pre指向null
		ListNode pre = null;
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			//记录当前节点的下一个节点
			tmp = cur.next;
			//然后将当前节点指向pre
			cur.next = pre;
   
			//pre和cur节点都前进一位
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
}