文章目錄

• • 單鏈表的反轉
  • • 1.頭插法
    • • 1.1思路
      • 1.2代碼實現
    • 2.就地逆置法
    • • 2.1思路
      • 2.2代碼實現

單鏈表的反轉

本文主要介紹頭插法逆置和就地逆置法實現鏈表的反轉

1.頭插法

1.1思路

迭代方式的鏈表反轉操作核心是從鏈表頭到鏈表尾

首先讓創建一個temp指針使其指向頭節點的下一個節點，并將其取出

取出之后讓新創建的reverseNode節點指向剛取出的節點，反復進行上述操作。需要注意的是每次取出節點之前，需要用另外一個指針暫存temp指向的節點的下一個節點，防止temp指針變化后找不到新的節點。

最后讓初始的頭節點指向初始鏈表中的尾節點。

1.2代碼實現

/*** 反轉鏈表*/public void reverseList(){//鏈表為空或者只有一個節點不需要反轉直接返回if (headNode.next == null || headNode.next.next == null){return;}//定義一個輔助指針遍歷原來的鏈表HeroNode temp = headNode.next;//指向temp指針指向的節點的下個節點HeroNode next = null;//新創建的頭節點HeroNode reverseHeadNode = new HeroNode(0,"","");//遍歷原來的鏈表,每遍歷一個節點,就將其取出,放在新的鏈表reverseHeadNode的最前端while (temp != null){//暫時保存當前節點的下一個節點,防止變化指針后找不到后續的數據next = temp.next;//讓temp的下一個節點指向新的鏈表的最前端 //reverseHeadNode->Null ------> reverseHeadNode->temp->Nulltemp.next = reverseHeadNode.next;reverseHeadNode.next = temp;//讓temp向后移動temp = next;}//將head.next指向reverseHeadNode.next 實現鏈表的反轉headNode.next = reverseHeadNode.next;}

---

2.就地逆置法

就地逆置法與頭插法思想類似，唯一區別在于頭插法是通過一個新鏈表頭來實現，而就地逆置法是直接通過遍歷鏈表對鏈表進行修改。

2.1思路

需要額外借助兩個指針（begin和end）

• 1.初始狀態下讓begin指向頭節點的下一個節點，end指向begin指向的下一個節點
  

• 將end指向的節點2從鏈表取出，添加至鏈表的頭部

• 將end -> begin.next，重復上述操作

此時begin指向的節點已成為鏈表尾，退出遍歷，完成逆置。

2.2代碼實現

/*** 就地逆置法反轉鏈表*/ public void reverse() {//如果鏈表為空或者鏈表中只有一個節點則不需要進行操作直接返回即可if (headNode.next == null || headNode.next.next == null){return;}HeroNode begin = headNode.next;HeroNode end = headNode.next.next;while (begin != null){//將end所指節點取出,beg指針指向end的下一個節點begin.next = end.next;//將end所指節點放入當前鏈表的頭部end.next = headNode.next;headNode.next = end;//將end指向下一個節點end = begin.next;} }

總結

以上是生活随笔為你收集整理的数据结构：单向链表的反转的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。