【LeetCode】206#反轉鏈表
題目描述
206#反轉鏈表
反轉一個單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階: 你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？
這是一個經典題目，《演算法》第四版有它的原題，在中文版第103頁1.3.30。
分析
這一題有兩種方法來做：遞歸法和迭代法。
遞歸法
思路
假設整個鏈表有N個節點，要將整個鏈表反轉，可以先將除第一個元素外的剩下N-1個元素先反轉，再把第一個元素插入到剩下鏈表的末尾。再將問題往下細分，直到遇到空節點。要注意到異常情況（鏈表為空或只有一個或兩個節點）。
源碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null) return null;
if (head.next == null) return head;
ListNode second = head.next;
ListNode rest = reverseList(second);
second.next = head;
head.next = null;
return rest;
}
}
迭代法
思路
我們需要設置三個節點，first,second,reverse。在每輪迭代中，我們從原鏈表中提取節點first並將它插入到逆鏈表的開頭。我們需要一直保持first指向原鏈表中所有剩餘節點的首節點，second指向原鏈表中所有剩餘節點的第二個節點，reverse指向結果鏈表的首節點。
源碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode first = head;
ListNode reverse = null;
while (first != null)
{
ListNode second = first.next;
first.next = reverse;
reverse = first;
first = second;
}
return reverse;
}
}
推薦閱讀：
