前沿:鏈表是面試中經(jīng)常問道的知識(shí)點(diǎn),比如鏈表反轉(zhuǎn),就地反轉(zhuǎn),判斷單鏈表是否相交,判斷鏈表是否有環(huán)等都是常問的問題.今天說一下單鏈表就地反轉(zhuǎn).
本文從包含頭節(jié)點(diǎn)和不包含頭節(jié)點(diǎn)兩種鏈表都提供了相應(yīng)的就地反轉(zhuǎn)方案:
頭節(jié)點(diǎn):數(shù)據(jù)結(jié)構(gòu)中，在單鏈表的開始結(jié)點(diǎn)之前附設(shè)一個(gè)類型相同的結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)歉闰。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息情臭，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向開始結(jié)點(diǎn)的指針（即第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置）令漂。
作用: 是為了方便單鏈表的特殊操作,比如插入,刪除等操作在鏈表在鏈表為null時(shí)操作具有特殊性.而使用了頭節(jié)點(diǎn)后就保持了單鏈表操作的統(tǒng)一性!
包含頭節(jié)點(diǎn)實(shí)現(xiàn)就地反轉(zhuǎn)
思路:1.如果頭節(jié)點(diǎn)為空,或者只有頭節(jié)點(diǎn)或者只有頭節(jié)點(diǎn)以及一個(gè)后繼節(jié)點(diǎn).這不需要反轉(zhuǎn),
2.如果有兩個(gè)以上的節(jié)點(diǎn)通過一個(gè)cur指針指向二個(gè)節(jié)點(diǎn),并將第一個(gè)節(jié)點(diǎn)的next指向null
3.如果cur節(jié)點(diǎn)不為null,通過另一個(gè)temp指針指向cur節(jié)點(diǎn)的的next節(jié)點(diǎn),(由于后面cur節(jié)點(diǎn)的next需要變化所以先保存下來)
4.將cur節(jié)點(diǎn)的next指向當(dāng)前的第一個(gè)節(jié)點(diǎn)(也就是head的next節(jié)點(diǎn))
5.將head節(jié)點(diǎn)的next節(jié)點(diǎn)指向cur節(jié)點(diǎn).
6.設(shè)置cur節(jié)點(diǎn)為temp節(jié)點(diǎn).從3開始循環(huán)
public static void reverse(Node head){
//步驟1
if (head==null||head.next==null||head.next.next==null){
return;
}
//步驟2
Node cur=head.next.next;
head.next.next=null;
while (cur!=null){
//步驟3
Node temp=cur.next;
//步驟4
cur.next=head.next;
//步驟5
head.next=cur;
//步驟6
cur=temp;
}
}
關(guān)于以上的主要思想其實(shí)就是:
當(dāng)除了頭節(jié)點(diǎn)外,沒有其他節(jié)點(diǎn)或者只有一個(gè)節(jié)點(diǎn)時(shí),鏈表不需要反轉(zhuǎn).
通過三個(gè)指針輔助執(zhí)行整個(gè)反轉(zhuǎn)過程,head用于指向頭節(jié)點(diǎn),cur指向當(dāng)前節(jié)點(diǎn),temp用于指向cur的next節(jié)點(diǎn).
將第一個(gè)節(jié)點(diǎn)(非head)的next指向null,因?yàn)樵诜崔D(zhuǎn)之后它為最后一個(gè)節(jié)點(diǎn)
將cur節(jié)點(diǎn)不斷的插入到head和第一個(gè)節(jié)點(diǎn)之間,并將cur指針指向temp不斷推進(jìn).
不包含頭節(jié)點(diǎn)實(shí)現(xiàn)就地反轉(zhuǎn)
private static Node revert(Node head) {
if (head == null || head.nextNode == null) {
// 到達(dá)尾結(jié)點(diǎn)
return head;
}
// 一直入棧
Node revertHead = revert(head.nextNode);
// 出棧并賦值nextNode對(duì)象
head.nextNode.nextNode = head;
head.nextNode = null;
// 返回尾結(jié)點(diǎn)（逆置后的頭結(jié)點(diǎn)）
return revertHead;
}
1.通過遞歸的方式找到尾節(jié)點(diǎn)(也就是反轉(zhuǎn)后的頭節(jié)點(diǎn))
2.從文件尾節(jié)點(diǎn)開始反向遍歷,每次都將自己的下一個(gè)節(jié)點(diǎn)指向自己,并將字節(jié)的next指向null.
