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

示例:

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

進(jìn)階:

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

1. 迭代方式

思路：

可以做到in-place的反轉(zhuǎn)。鏈表反轉(zhuǎn)后，實(shí)際上只是中間節(jié)點(diǎn)的指針?lè)崔D(zhuǎn)，并且反轉(zhuǎn)后原來(lái)鏈表的頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)應(yīng)該為NULL，而反轉(zhuǎn)后鏈表的頭結(jié)點(diǎn)為原來(lái)鏈表的尾節(jié)點(diǎn)。我們可以從頭結(jié)點(diǎn)開始，每次處理兩個(gè)節(jié)點(diǎn)之間的一個(gè)指針，將其反轉(zhuǎn)過(guò)來(lái)。然后再處理接下來(lái)兩個(gè)節(jié)點(diǎn)之間的指針……直至遇到尾節(jié)點(diǎn)，設(shè)置為新鏈表的頭結(jié)點(diǎn)即可。

實(shí)現(xià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 rHead = null; // 反轉(zhuǎn)后的頭節(jié)點(diǎn)
        ListNode curr = head; // 當(dāng)前處理節(jié)點(diǎn)
        ListNode pTail = null; // 反轉(zhuǎn)后尾節(jié)點(diǎn)
        while (curr != null) {
            ListNode tmp = curr.next;
            if (tmp == null) {
                rHead = curr;
            }
            curr.next = pTail;
            pTail = curr;
            curr = tmp;
        }
        
        return rHead;
    }
}

2. 遞歸方式：

/**
 * 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 || head.next == null) {
            return head;
        }
        
        ListNode rHead = reverseList(head.next); // 反轉(zhuǎn)得到新鏈表的頭節(jié)點(diǎn)
        head.next.next = head; // 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的next指針?lè)崔D(zhuǎn)過(guò)來(lái)
        head.next = null; // 設(shè)置新鏈表的尾節(jié)點(diǎn)
    
        return rHead;
    }
}