題目

Reverse a singly linked list.

Example:

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

翻譯

反轉(zhuǎn)單鏈表

迭代方式

在這里我們定義了三個(gè)指針。指向前一個(gè)節(jié)點(diǎn)的pre蛙奖。指向當(dāng)前節(jié)點(diǎn)的cur亮垫。和指向下一節(jié)點(diǎn)的next。pre指針初始化時(shí)候指向空指針躺涝。

之后我們讓當(dāng)前cur指針改向厨钻。指向pre指針进肯。pre指針在這里的作用主要是保存上一個(gè)節(jié)點(diǎn)的信息首繁。

我們讓pre指針指向cur指針。cur指針指向next指針回俐。next通過(guò)節(jié)點(diǎn)自身的下一個(gè)元素指向下一個(gè)元素苍蔬。相當(dāng)于三個(gè)指針都向前走了一步诱建。

具體代碼如下

// 206. Reverse Linked List
// https://leetcode.com/problems/reverse-linked-list/description/
// 時(shí)間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(1)
public class Solution1 {

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

    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

遞歸方式

前面非遞歸方式是從前面數(shù)1開(kāi)始往后依次處理押袍，而遞歸方式則恰恰相反，它先循環(huán)找到最后面指向的數(shù)5凯肋，然后從5開(kāi)始處理依次翻轉(zhuǎn)整個(gè)鏈表伯病。
　　首先指針H迭代到底，如下圖所示，并且設(shè)置一個(gè)新的指針作為翻轉(zhuǎn)后的鏈表的頭午笛。由于整個(gè)鏈表翻轉(zhuǎn)之后的頭就是最后一個(gè)數(shù)惭蟋，所以整個(gè)過(guò)程N(yùn)ewH指針一直指向存放5的地址空間。

　然后H指針逐層返回的時(shí)候依次做下圖的處理药磺，將H指向的地址賦值給H->next->next指針告组，并且一定要記得讓H->next =NULL，也就是斷開(kāi)現(xiàn)在指針的鏈接癌佩，否則新的鏈表形成了環(huán)木缝，下一層H->next->next賦值的時(shí)候會(huì)覆蓋后續(xù)的值。

代碼如下：

// 206. Reverse Linked List
// https://leetcode.com/problems/reverse-linked-list/description/
// 遞歸的方式反轉(zhuǎn)鏈表
// 時(shí)間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(n) 
public class Solution2 {

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

    public ListNode reverseList(ListNode head) {

        // 遞歸終止條件
        if(head == null|| head.next == null)
            return head;

        ListNode rhead = reverseList(head.next);

        // head->next此刻指向head后面的鏈表的尾節(jié)點(diǎn)
        // head->next->next = head把head節(jié)點(diǎn)放在了尾部
        head.next.next = head;
        head.next = null;

        return rhead;
    }
}