單鏈表的反轉是常見的面試題目。本文總結了2種方法。

1 定義

單鏈表node的數據結構定義如下：

class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;} }

2 方法1：就地反轉法

2.1 思路

把當前鏈表的下一個節點pCur插入到頭結點dummy的下一個節點中，就地反轉。

dummy->1->2->3->4->5的就地反轉過程：

dummy->2->1->3->4->5 dummy->3->2->1->4->5 dummy->4>-3->2->1->5 dummy->5->4->3->2->1

2.2 解釋

1初始狀態

2 過程

pCur是需要反轉的節點。

prev連接下一次需要反轉的節點

反轉節點pCur

糾正頭結點dummy的指向

pCur指向下一次要反轉的節點

偽代碼

1 prev.next = pCur.next; 2 pCur.next = dummy.next; 3 dummy.next = pCur; 4 pCur = prev.next;

3 循環條件

pCur is not null

2.3 代碼

// 1.就地反轉法public ListNode reverseList1(ListNode head) {if (head == null)return head;ListNode dummy = new ListNode(-1);dummy.next = head;ListNode prev = dummy.next;ListNode pCur = prev.next;while (pCur != null) {prev.next = pCur.next;pCur.next = dummy.next;dummy.next = pCur;pCur = prev.next;}return dummy.next;}

2.4 總結

• 1個頭結點，2個指針，4行代碼
• 注意初始狀態和結束狀態，體會中間的圖解過程。

3 方法2：新建鏈表，頭節點插入法

3.1 思路

新建一個頭結點，遍歷原鏈表，把每個節點用頭結點插入到新建鏈表中。最后，新建的鏈表就是反轉后的鏈表。

3.2 解釋

1 初始狀態

3 方法2：新建鏈表，頭節點插入法

3.1 思路

新建一個頭結點，遍歷原鏈表，把每個節點用頭結點插入到新建鏈表中。最后，新建的鏈表就是反轉后的鏈表。

3.2 解釋

1 初始狀態

2 過程

pCur是要插入到新鏈表的節點。

pNex是臨時保存的pCur的next。

pNex保存下一次要插入的節點

把pCur插入到dummy中

糾正頭結點dummy的指向

pCur指向下一次要插入的節點

偽代碼

1 pNex = pCur.next 2 pCur.next = dummy.next 3 dummy.next = pCur 4 pCur = pNex

3 循環條件

pCur is not null

3.3 代碼

// 2.新建鏈表,頭節點插入法public ListNode reverseList2(ListNode head) {ListNode dummy = new ListNode(-1);ListNode pCur = head;while (pCur != null) {ListNode pNex = pCur.next;pCur.next = dummy.next;dummy.next = pCur;pCur = pNex;}return dummy.next;}

3.4 總結

• 1個頭結點，2個指針（包含一個臨時保存節點的pNex），4行代碼
• 注意初始狀態和結束狀態，體會中間的圖解過程。

總結

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

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