LeetCode 反轉(zhuǎn)鏈表 [簡單]

定義一個函數(shù)，輸入一個鏈表的頭節(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof

示例:

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

限制：

0 <= 節(jié)點個數(shù) <= 5000

題目分析

解答1

使用外部空間 先把數(shù)據(jù)拿出來，然后再把數(shù)據(jù)放回去

解答2

雙指針迭代
請兩個指針，第一個指針叫 pre，最初是指向 null 的。
第二個指針 cur 指向 head，然后不斷遍歷 cur。
每次迭代到 cur，都將 cur 的 next 指向 pre，然后 pre 和 cur 前進一位。
都迭代完了(cur 變成 null 了)，pre 就是最后一個節(jié)點了。
動畫演示如下

解答3

遞歸解法

以上解法來自：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/dong-hua-yan-shi-duo-chong-jie-fa-206-fan-zhuan-li/

代碼實現(xiàn)

public class ReverseList {

    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head, tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}