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

示例:

限制：

鏈表的反轉(zhuǎn)是老生常談的一個(gè)問題了，同時(shí)也是面試中常考的一道題。最簡(jiǎn)單的一種方式就是使用棧，因?yàn)?strong>棧是先進(jìn)后出的。實(shí)現(xiàn)原理就是把鏈表節(jié)點(diǎn)一個(gè)個(gè)入棧，當(dāng)全部入棧完之后再一個(gè)個(gè)出棧，出棧的時(shí)候在把出棧的結(jié)點(diǎn)串成一個(gè)新的鏈表。原理如下

   

代碼比較簡(jiǎn)單，來看下

 1public ListNode reverseList(ListNode head) {
2    Stack<ListNode> stack = new Stack<>();
3    //把鏈表節(jié)點(diǎn)全部摘掉放到棧中
4    while (head != null) {
5        stack.push(head);
6        head = head.next;
7    }
8    if (stack.isEmpty())
9        return null;
10    ListNode node = stack.pop();
11    ListNode dummy = node;
12    //棧中的結(jié)點(diǎn)全部出棧，然后重新連成一個(gè)新的鏈表
13    while (!stack.isEmpty()) {
14        ListNode tempNode = stack.pop();
15        node.next = tempNode;
16        node = node.next;
17    }
18    //最后一個(gè)結(jié)點(diǎn)就是反轉(zhuǎn)前的頭結(jié)點(diǎn)，一定要讓他的next
19    //等于空，否則會(huì)構(gòu)成環(huán)
20    node.next = null;
21    return dummy;
22}

雙鏈表求解是把原鏈表的結(jié)點(diǎn)一個(gè)個(gè)摘掉，每次摘掉的鏈表都讓他成為新的鏈表的頭結(jié)點(diǎn)，然后更新新鏈表。下面以鏈表1→2→3→4為例畫個(gè)圖來看下。

 1public ListNode reverseList(ListNode head) {
2    //新鏈表
3    ListNode newHead = null;
4    while (head != null) {
5        //先保存訪問的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，保存起來
6        //留著下一步訪問的
7        ListNode temp = head.next;
8        //每次訪問的原鏈表節(jié)點(diǎn)都會(huì)成為新鏈表的頭結(jié)點(diǎn)，
9        //其實(shí)就是把新鏈表掛到訪問的原鏈表節(jié)點(diǎn)的
10        //后面就行了
11        head.next = newHead;
12        //更新新鏈表
13        newHead = head;
14        //重新賦值，繼續(xù)訪問
15        head = temp;
16    }
17    //返回新鏈表
18    return newHead;
19}

我們?cè)賮砘仡櫼幌逻f歸的模板，終止條件，遞歸調(diào)用，邏輯處理。

 1public ListNode reverseList(參數(shù)0) {
2    if (終止條件)
3        return;
4
5    邏輯處理（可能有，也可能沒有，具體問題具體分析）
6
7    //遞歸調(diào)用
8    ListNode reverse = reverseList(參數(shù)1);
9
10    邏輯處理（可能有，也可能沒有，具體問題具體分析）
11}

if (head == null || head.next == null)    return head;

 1public ListNode reverseList(ListNode head) {
2    //終止條件
3    if (head == null || head.next == null)
4        return head;
5    //保存當(dāng)前節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
6    ListNode next = head.next;
7    //從當(dāng)前節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始遞歸調(diào)用
8    ListNode reverse = reverseList(next);
9    //reverse是反轉(zhuǎn)之后的鏈表，因?yàn)楹瘮?shù)reverseList
10    // 表示的是對(duì)鏈表的反轉(zhuǎn)，所以反轉(zhuǎn)完之后next肯定
11    // 是鏈表reverse的尾結(jié)點(diǎn)，然后我們?cè)侔旬?dāng)前節(jié)點(diǎn)
12    //head掛到next節(jié)點(diǎn)的后面就完成了鏈表的反轉(zhuǎn)。
13    next.next = head;
14    //這里head相當(dāng)于變成了尾結(jié)點(diǎn)，尾結(jié)點(diǎn)都是為空的，
15    //否則會(huì)構(gòu)成環(huán)
16    head.next = null;
17    return reverse;
18}

1public ListNode reverseList(ListNode head) {
2    if (head == null || head.next == null)
3        return head;
4    ListNode reverse = reverseList(head.next);
5    head.next.next = head;
6    head.next = null;
7    return reverse;
8}

 1public ListNode reverseList(ListNode head) {
2    return reverseListInt(head, null);
3}
4
5private ListNode reverseListInt(ListNode head, ListNode newHead) {
6    if (head == null)
7        return newHead;
8    ListNode next = head.next;
9    head.next = newHead;
10    return reverseListInt(next, head);
11}

 1public ListNode reverseList(ListNode head) {
2    return reverseListInt(head, null);
3}
4
5private ListNode reverseListInt(ListNode head, ListNode newHead) {
6    if (head == null)
7        return newHead;
8    ListNode next = head.next;
9    head.next = newHead;
10    ListNode node = reverseListInt(next, head);
11    return node;
12}