問(wèn)題1： 整體鏈表反轉(zhuǎn)
假設(shè)存在鏈表 1 → 2 → 3 → ?，我們想要把它改成 ? ← 1 ← 2 ← 3。

在遍歷列表時(shí)，將當(dāng)前節(jié)點(diǎn)的 next 指針改為指向前一個(gè)元素。由于節(jié)點(diǎn)沒(méi)有引用其上一個(gè)節(jié)點(diǎn)，因此必須事先存儲(chǔ)其前一個(gè)元素。在更改引用之前，還需要另一個(gè)指針來(lái)存儲(chǔ)下一個(gè)節(jié)點(diǎn)。不要忘記在最后返回新的頭引用！

image.png

關(guān)鍵
將當(dāng)前節(jié)點(diǎn)的指針指向上一個(gè)節(jié)點(diǎn)
然后更新當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的值即順移
技巧
設(shè)置哨兵節(jié)點(diǎn) null，初始化時(shí)將head節(jié)點(diǎn)指向null，下一步將next指向head
重復(fù)以上動(dòng)作直到當(dāng)前節(jié)點(diǎn)為尾節(jié)點(diǎn)的節(jié)點(diǎn)null

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

復(fù)雜度分析

時(shí)間復(fù)雜度：O(n)，假設(shè) n 是列表的長(zhǎng)度，時(shí)間復(fù)雜度是 O(n)。
空間復(fù)雜度：O(1)。

問(wèn)題2：鏈表部分反轉(zhuǎn)
對(duì)于鏈表的問(wèn)題，根據(jù)以往的經(jīng)驗(yàn)一般都是要建一個(gè)dummy node，連上原鏈表的頭結(jié)點(diǎn)，這樣的話就算頭結(jié)點(diǎn)變動(dòng)了，我們還可以通過(guò)dummy->next來(lái)獲得新鏈表的頭結(jié)點(diǎn)。這道題的要求是只通過(guò)一次遍歷完成，就拿題目中的例子來(lái)說(shuō)，變換的是2,3,4這三個(gè)點(diǎn)，我們需要找到第一個(gè)開(kāi)始變換結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，只要讓pre向后走m-1步即可，為啥要減1呢，因?yàn)轭}目中是從1開(kāi)始計(jì)數(shù)的，這里只走了1步，就是結(jié)點(diǎn)1，用pre指向它。萬(wàn)一是結(jié)點(diǎn)1開(kāi)始變換的怎么辦，這就是我們?yōu)樯兑胐ummy結(jié)點(diǎn)了，pre也可以指向dummy結(jié)點(diǎn)。然后就要開(kāi)始交換了，由于一次只能交換兩個(gè)結(jié)點(diǎn)，所以我們按如下的交換順序：

1 -> 2 -> 3 -> 4 -> 5 -> NULL

1 -> 3 -> 2 -> 4 -> 5 -> NULL

1 -> 4 -> 3 -> 2 -> 5 -> NULL

我們可以看出來(lái)，總共需要n-m步即可，第一步是將結(jié)點(diǎn)3放到結(jié)點(diǎn)1的后面，第二步將結(jié)點(diǎn)4放到結(jié)點(diǎn)1的后面。這是很有規(guī)律的操作，那么我們就說(shuō)一個(gè)就行了，比如剛開(kāi)始，pre指向結(jié)點(diǎn)1，cur指向結(jié)點(diǎn)2，然后我們建立一個(gè)臨時(shí)的結(jié)點(diǎn)t，指向結(jié)點(diǎn)3（注意我們用臨時(shí)變量保存某個(gè)結(jié)點(diǎn)就是為了首先斷開(kāi)該結(jié)點(diǎn)和前面結(jié)點(diǎn)之間的聯(lián)系，這可以當(dāng)作一個(gè)規(guī)律記下來(lái)），然后我們斷開(kāi)結(jié)點(diǎn)2和結(jié)點(diǎn)3，將結(jié)點(diǎn)2的next連到結(jié)點(diǎn)4上，也就是 cur->next = t->next，再把結(jié)點(diǎn)3連到結(jié)點(diǎn)1的后面結(jié)點(diǎn)（即結(jié)點(diǎn)2）的前面，即 t->next = pre->next，最后再將原來(lái)的結(jié)點(diǎn)1和結(jié)點(diǎn)2的連接斷開(kāi)，將結(jié)點(diǎn)1連到結(jié)點(diǎn)3，即 pre->next = t。這樣我們就完成了將結(jié)點(diǎn)3取出，加入結(jié)點(diǎn)1的后方。第二步將結(jié)點(diǎn)4取出，加入結(jié)點(diǎn)1的后方，也是同樣的操作，這里就不多說(shuō)了，請(qǐng)大家自己嘗試下吧，參考代碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public  ListNode* reverseBetween(ListNode* head, int m, int n) {
        int len = n - m;
        ListNode* root=new ListNode(-1);
        root.next = head;    
        ListNode* pre=root;
        ListNode* cur=head;
        int count = 1;
        
        while (cur != null) {
            if (count < m) {
                pre = cur;
                cur = cur.next;
                count++;
            } else if (count == m) {
                for (int j=0;j<len;j++) {
                    ListNode* tmp=cur.next;
                    cur.next = tmp.next;
                    tmp.next = pre.next;
                    pre.next = tmp;
                }
                break;
            }
        }
        
        return root.next;
    }
};