LeetCode 206 反轉鏈表

我們首先看一下題目

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

這道題目是反轉鏈表，那麼先說一下常規思維是怎樣的

方法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是需要反轉的節點。

1. prev連接下一次需要反轉的節點
2. 反轉節點pCur
3. 糾正頭結點dummy的指向
4. 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 // 1.就地反轉法
 2 public ListNode reverseList1(ListNode head) {
 3 if (head == null)
 4 return head;
 5 ListNode dummy = new ListNode(-1);
 6 dummy.next = head;
 7 ListNode prev = dummy.next;
 8 ListNode pCur = prev.next;
 9 while (pCur != null) {
10 prev.next = pCur.next;
11 pCur.next = dummy.next;
12 dummy.next = pCur;
13 pCur = prev.next;
14 }
15 return dummy.next;
16 }

2.4 總結

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

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

3.1 思路

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

3.2 解釋

1 初始狀態

2 過程

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

pNex是臨時保存的pCur的next。

1. pNex保存下一次要插入的節點
2. 把pCur插入到dummy中
3. 糾正頭結點dummy的指向
4. pCur指向下一次要插入的節點

偽代碼

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

3 循環條件

pCur is not null

3.3 代碼

 1 // 2.新建鏈表,頭節點插入法
 2 public ListNode reverseList2(ListNode head) {
 3 ListNode dummy = new ListNode(-1);
 4 ListNode pCur = head;
 5 while (pCur != null) {
 6 ListNode pNex = pCur.next;
 7 pCur.next = dummy.next;
 8 dummy.next = pCur;
 9 pCur = pNex;
10 }
11 return dummy.next;
12 }l

可見，邏輯非常複雜，下面我們要講一個簡單方法，遞歸反轉法

如何遞歸反轉哪？假設有2個節點，只需要將第二個節點指向第一個，鏈表頭指向第二個節點即可。

那麼試想一下，假設將剩下的節點，都看成第一個節點那麼問題就簡單了

直接上代碼吧

class Solution {
public:
 ListNode *we;
 ListNode *reverseList(ListNode *head) {
 if (head== nullptr||head->next== nullptr)
 {
 return head;
 }
 ListNode *p = head;
 ListNode *l = head->next;
 reverce(l, p);
 head->next = nullptr;
 return we;
 }
 void reverce(ListNode *l, ListNode *p) {
 if (l->next != nullptr) {
 reverce(l->next, p->next);
 } else
 {
 we = l;
 }
 l->next = p; 

 }
};

閱讀更多 青峰科技 的文章

關鍵字: 題目 prev 鏈表