利用頭插法能重新建立帶頭節(jié)點(diǎn)的新鏈表

下面簡單介紹一下，算法思想結(jié)合圖示看

算法思想：逆置鏈表初始為空，表中節(jié)點(diǎn)從原鏈表中依次“刪除”，再逐個(gè)插入逆置鏈表的表頭（即“頭插”到逆置鏈表中），使它成為逆置鏈表的“新”的第一個(gè)結(jié)點(diǎn)，如此循環(huán)，直至原鏈表為空。

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;
}

接下來，進(jìn)行圖解：

剛開始是這樣

進(jìn)入循環(huán)，分別用q和p記錄第一個(gè)和第二個(gè)節(jié)點(diǎn)

 進(jìn)入第二輪循環(huán)，這是發(fā)生重大變化的關(guān)鍵時(shí)期

 這張圖調(diào)整一下

 直到鏈表為空

這篇文章已經(jīng)一年半了，還是源源不斷有不同的評(píng)論，去探討相關(guān)的問題，其實(shí)圖解不一定清晰。下面用更簡明的方式給大家說一下什么情況。

這里采用Java的寫法，C一定也能看懂。

我首先創(chuàng)建三個(gè)節(jié)點(diǎn)，一個(gè)是當(dāng)前節(jié)點(diǎn)cur、一個(gè)是cur上一個(gè)節(jié)點(diǎn)pre。另外就是tmp。

每次循環(huán)，我用tmp記錄cur下一個(gè)節(jié)點(diǎn)，接著將cur的next指針指向上一個(gè)節(jié)點(diǎn)pre。這個(gè)時(shí)候就完成了一次反轉(zhuǎn)操作。

接著將pre和cur的記錄往后移動(dòng)一次，重復(fù)上面的操作。

直至達(dá)到鏈表結(jié)尾。

class Solution {
	public ListNode reverseList(ListNode head) {
		//申請節(jié)點(diǎn)，pre和 cur，pre指向null
		ListNode pre = null;
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			//記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
			tmp = cur.next;
			//然后將當(dāng)前節(jié)點(diǎn)指向pre
			cur.next = pre;
			//pre和cur節(jié)點(diǎn)都前進(jìn)一位
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
}