題目描述

給你單鏈表的頭節(jié)點(diǎn) head ，請(qǐng)你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]
輸出：[2,1]

示例 3：

輸入：head = []
輸出：[]

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 5000]
• -5000 <= Node.val <= 5000

解法一

思路：

迭代置換，p,q,r三個(gè)指針，轉(zhuǎn)換q.next=p，之后p=q,q=r,r=r.next。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p,q,r;
        p = head;q=head.next;r=head.next.next;
        while(true){
            if(p==head)p.next=null;
            q.next=p;
            p=q;
            q=r;
            if(q==null) break;
            r=r.next;
        }
        return p;
    }
}

解法二

思路：

來自官方解答。

遞歸版本稍微復(fù)雜一些，其關(guān)鍵在于反向工作。假設(shè)鏈表的其余部分已經(jīng)被反轉(zhuǎn)，現(xiàn)在應(yīng)該反轉(zhuǎn)它前面的部分。設(shè)鏈表為：

若從節(jié)點(diǎn) 到 已經(jīng)被反轉(zhuǎn)，而我們正處于 。

我們希望 的下一個(gè)節(jié)點(diǎn)指向

所以，

需要注意的是 的下一個(gè)節(jié)點(diǎn)必須指向 ?。如果忽略了這一點(diǎn)，鏈表中可能會(huì)產(chǎn)生環(huán)

代碼：

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}