算法（5）- 鏈表一【翻轉(zhuǎn)鏈表】

說在前面：

1半夷、鏈表不支持隨機的訪問元素胳挎，需從頭一次遍歷到要訪問的節(jié)點饼疙。
2、思路
（1）設(shè)立頭結(jié)點慕爬。
（2）借助輔助指針窑眯，修改節(jié)點的next指針實現(xiàn)。（穿針引線）
（3）刪除當(dāng)前節(jié)點医窿，且前一節(jié)點未知時磅甩。可將后一節(jié)點的值賦給當(dāng)前節(jié)點姥卢，再刪除后一節(jié)點卷要。
（4）不改變鏈表結(jié)構(gòu)，通過修改節(jié)點值實現(xiàn)（一般不這樣）
2独榴、注意（1）與（2）的區(qū)別僧叉。

（1）ListNode cur = L1;
（2）ListNode cur = null;    cur.next = L1;

3、鏈表初始化及打印

       // 初始化head鏈表
        ListNode head = new ListNode(2);
        ListNode current = head;
        for (int j = 3; j < 10; j++) {
            current .next = new ListNode(j);
            current = current .next;
        }

      // 打印鏈表head
       ListNode resout = head;
        while (resout != null){
            System.out.println(resout.val);
            resout = resout.next;
        }

一棺榔、翻轉(zhuǎn)鏈表例題

1. 206 翻轉(zhuǎn)鏈表 Reverse Linked List

題目：反轉(zhuǎn)一個單鏈表瓶堕。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題症歇？

一般來說捞烟，鏈表相關(guān)不能只改變節(jié)點的值，而應(yīng)該改變next指針實現(xiàn)当船。
設(shè)立指針（引用）

題意.png

思路

（1）利用三個輔助指針题画，修改節(jié)點的next指針實現(xiàn)。

    public static ListNode reverseList(ListNode head) {
        /**
         *  利用三個輔助指針德频，修改節(jié)點的next指針實現(xiàn)苍息。
         * 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
         * 內(nèi)存消耗：39.5 MB, 在所有 Java 提交中擊敗了5.06% 的用戶
         */
        ListNode pre = head;
        ListNode cur = null;
        ListNode nex = null;
        if (pre != null){
            cur = head.next;
        }
        if (cur != null){
            nex = cur.next;
        }
        head.next = null;
        while (cur != null){
            cur.next = pre;
            pre = cur;
            cur = nex;
            if (nex != null){
                nex = nex.next;
            }
        }
        // ————測試輸出節(jié)點
        ListNode resout = pre;
        while (resout != null){
            System.out.println(resout.val);
            resout = resout.next;
        }
        return resout;
}

（2）通過修改節(jié)點的值實現(xiàn)翻轉(zhuǎn)。

 /**
         *  通過修改節(jié)點的值實現(xiàn)翻轉(zhuǎn)壹置。輔助 HashMap 記錄節(jié)點值竞思，再反向賦給節(jié)點。
         * 執(zhí)行用時：2 ms, 在所有 Java 提交中擊敗了5.09% 的用戶
         * 內(nèi)存消耗：39.3 MB, 在所有 Java 提交中擊敗了5.06% 的用戶
         */
        Map<Integer, Integer> a = new HashMap<Integer, Integer>();
        int b = 0;
        // 用map記錄節(jié)點的值
        ListNode cur = head;
        while (cur != null){
            a.put(b,cur.val);
            b++;
            cur = cur.next;
        }
        // 依次修改節(jié)點的值
        cur = head;
        while (cur !=null){
            cur.val = a.get(--b);
            cur = cur.next;
        }
        // 輸出打印節(jié)點
        cur = head;
        while (cur!=null){
            System.out.println(cur.val);
            cur = cur.next;
        }
        return head;

C++解題示例

2. 92 反轉(zhuǎn)鏈表II Reverse Linked List II ——比較復(fù)雜

題目：
反轉(zhuǎn)從位置 m 到 n 的鏈表钞护。請使用一趟掃描完成反轉(zhuǎn)盖喷。
說明:1 ≤ m ≤ n ≤ 鏈表長度。
示例:
輸入: 1->2->3->4->5->NULL, m = 2, n = 4
輸出: 1->4->3->2->5->NULL

本題借助五個“指針”难咕，注意越界問題课梳，及循環(huán)條件距辆。
注意特殊情況，如m=n暮刃，n=最后一個節(jié)點等等跨算。

思路

 public static ListNode reverseBetween(ListNode head, int m, int n) {
        /**
         * 反轉(zhuǎn)從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉(zhuǎn)椭懊。
         * 1 ≤ m ≤ n ≤ 鏈表長度诸蚕。
         * 執(zhí)行用時：0 ms, 在所有 Java 提交中擊敗了100.00% 的用戶
         * 內(nèi)存消耗：37.4 MB, 在所有 Java 提交中擊敗了8.70% 的用戶
         */
        if (m==n){
            return head;
        }
        ListNode pre = null;
        ListNode first = null;
        ListNode cur = head;   // 當(dāng)前節(jié)點，與下面a相等
        ListNode nex = null;   // 下一節(jié)點氧猬，
        ListNode last = null;  // 下下節(jié)點背犯，用于找到nex
        if (cur.next != null){
            nex = cur.next;
        }
        int a = 1;   
        // 當(dāng)a屬于[m,n]中，并且nex不為空盅抚，或者a = n（即n是最后一個節(jié)點時）
        while ((nex != null && a<n+1) || a==n){
            if (a==m-1){
                pre = cur;
                first = nex;
            }
            if (a<m){
                cur = nex;
                if (nex.next != null){
                    nex = nex.next;
                }
            }
            if (m==1){
                first = head;
                pre = head;
            }
            if (a>=m && a<n){
                // a>=m a<n 時媳板，cur指針后移，nex指針后移泉哈，a++蛉幸，nex指針
                last = nex.next;
                nex.next = cur;
                cur = nex;
                nex = last;
            }
            if (a == n){
                pre.next = cur;
                first.next = nex;
                if (m==1){
                    head = cur;
                }
            }
            a++;
        }
        return head;
    }

3. 328 奇偶鏈表

題目：給定一個單鏈表，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起丛晦。請注意奕纫，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性，而不是節(jié)點的值的奇偶性烫沙。
請嘗試使用原地算法完成匹层。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時間復(fù)雜度應(yīng)為 O(nodes)锌蓄，nodes 為節(jié)點總數(shù)升筏。
示例 1:
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL

算法思路：設(shè)置三個輔助指針，先找到奇數(shù)偶數(shù)節(jié)點的next指針瘸爽，再將奇節(jié)點的最后一個指針指向偶數(shù)節(jié)點的第一個指針您访。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode nowNode = head;
        ListNode secNode = null;
        ListNode nowSecNode = null;
        if(head == null){
            return head;
        }
        if(head.next != null){
            System.out.println("000000");
            secNode = head.next;    // 第二個節(jié)點
            nowSecNode = head.next; 
        }else{
            return head;
        }
// 先不管奇數(shù)最后一個指針，先排好兩個鏈表剪决。然后再連起來
        while(nowNode.next != null && nowNode.next.next != null){
            nowSecNode = nowNode.next;
            nowNode.next = nowSecNode.next;
            nowNode = nowSecNode.next;
            nowSecNode.next = nowNode.next;
        }
        nowNode.next = secNode;
        return head;
    }
}