題目描述

206#反轉(zhuǎn)鏈表

反轉(zhuǎn)一個(gè)單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

這是一個(gè)經(jīng)典題目，《算法》第四版有它的原題，在中文版第103頁(yè)1.3.30。

分析

這一題有兩種方法來(lái)做：遞歸法和迭代法。

遞歸法

思路

假設(shè)整個(gè)鏈表有N個(gè)節(jié)點(diǎn)，要將整個(gè)鏈表反轉(zhuǎn)，可以先將除第一個(gè)元素外的剩下N-1個(gè)元素先反轉(zhuǎn)，再把第一個(gè)元素插入到剩下鏈表的末尾。再將問(wèn)題往下細(xì)分，直到遇到空節(jié)點(diǎn)。要注意到異常情況（鏈表為空或只有一個(gè)或兩個(gè)節(jié)點(diǎn)）。

源碼

/**
 * 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;
    }
}

迭代法

思路

我們需要設(shè)置三個(gè)節(jié)點(diǎn)，first,second,reverse。在每輪迭代中，我們從原鏈表中提取節(jié)點(diǎn)first并將它插入到逆鏈表的開頭。我們需要一直保持first指向原鏈表中所有剩余節(jié)點(diǎn)的首節(jié)點(diǎn)，second指向原鏈表中所有剩余節(jié)點(diǎn)的第二個(gè)節(jié)點(diǎn)，reverse指向結(jié)果鏈表的首節(jié)點(diǎn)。

源碼

/**
 * 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;
    }
}