反轉(zhuǎn)鏈表

題目：定義一個函數(shù)，輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點。

鏈表結(jié)點定義如下：

public static class ListNode {
    int value;
    ListNode next;
}

解題思路：

在單鏈表的表頭臨時接入一個節(jié)點，然后進(jìn)行尾插法操作。反轉(zhuǎn)單鏈表。

代碼實現(xiàn)：

public class Test16 {
    public static class ListNode {
        int value;
        ListNode next;
    }
    /**
     * 定義一個函數(shù)，輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點。
     *
     * @param head 鏈表的頭結(jié)點
     * @return 反轉(zhuǎn)后的鏈表的頭結(jié)點
     */
    public static ListNode reverseList(ListNode head) {
        // 創(chuàng)建一個臨時結(jié)點，當(dāng)作尾插法的邏輯頭結(jié)點
        ListNode root = new ListNode();
        // 邏輯頭結(jié)點點的下一個結(jié)點為空
        root.next = null;
        // 用于記錄要處理的下一個結(jié)點
        ListNode next;
        // 當(dāng)前處理的結(jié)點不為空
        while (head != null) {
            // 記錄要處理的下一個結(jié)點
            next = head.next;
            // 當(dāng)前結(jié)點的下一個結(jié)點指向邏輯頭結(jié)點的下一個結(jié)點
            head.next = root.next;
            // 邏輯頭結(jié)點的下一個結(jié)點指向當(dāng)前處理的結(jié)點
            root.next = head;
            // 上面操作完成了一個結(jié)點的頭插
            // 當(dāng)前結(jié)點指向下一個要處理的結(jié)點
            head = next;
        }
        // 邏輯頭結(jié)點的下一個結(jié)點就是返回后的頭結(jié)點
        return root.next;
    }
    /**
     * 定義一個函數(shù)，輸入一個鏈表的頭結(jié)點，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭結(jié)點。
     * 【書本上的方法，不使用邏輯頭結(jié)點】
     *
     * @param head 鏈表的頭結(jié)點
     * @return 反轉(zhuǎn)后的鏈表的頭結(jié)點
     */
    public static ListNode reverseList2(ListNode head) {
        // 用于記錄反轉(zhuǎn)后的鏈表的頭結(jié)點
        ListNode reverseHead = null;
        // 用于記錄當(dāng)前處理的結(jié)點的
        ListNode curr = head;
        // 用于記錄當(dāng)前結(jié)點的前驅(qū)結(jié)點
        // 前驅(qū)結(jié)點開始為null，因為了是反轉(zhuǎn)后的最后一個結(jié)點的下一個結(jié)點，即null
        ListNode prev = null;
        // 當(dāng)前結(jié)點的下一個結(jié)點
        ListNode next;
        // 對鏈表進(jìn)行尾插法操作
        while (curr != null) {
            // 記錄當(dāng)前處理的結(jié)點，最后一個記錄的結(jié)點就是反轉(zhuǎn)后的頭結(jié)點
            // 【注意：與書上的不同，因為curr.next=null時，curr此時就最后一個處理的結(jié)點，
            // 對應(yīng)到反轉(zhuǎn)后的鏈表就是第一個結(jié)點，書上那樣做更精確，只是多了一些判斷，可以不要if】
            reverseHead = curr;
            // 記錄當(dāng)然前下一個結(jié)點
            next = curr.next;
            // 當(dāng)前結(jié)點的下一個結(jié)點指向前驅(qū)結(jié)點，這樣當(dāng)前結(jié)點就插入到了反轉(zhuǎn)鏈表的頭部
            curr.next = prev;
            // 記錄當(dāng)前結(jié)點為前驅(qū)結(jié)點
            prev = curr;
            // 當(dāng)前結(jié)點點移動到下一個結(jié)點
            curr = next;
        }
        // 返回轉(zhuǎn)后的頭結(jié)點
        return reverseHead;
    }
    /**
     * 輸出鏈表的元素值
     *
     * @param head 鏈表的頭結(jié)點
     */
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }
    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.value = 1;
        head.next = new ListNode();
        head.next.value = 2;
        head.next.next = new ListNode();
        head.next.next.value = 3;
        head.next.next.next = new ListNode();
        head.next.next.next.value = 4;
        head.next.next.next.next = new ListNode();
        head.next.next.next.next.value = 5;
        head.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.value = 6;
        head.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.value = 7;
        head.next.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.next.value = 8;
        head.next.next.next.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.next.next.next.value = 9;
        printList(head);
        head = reverseList(head);
        printList(head);
        head = reverseList2(head);
        printList(head);
    }
}

運行結(jié)果：

http://wiki.jikexueyuan.com/project/for-offer/images/21.png" alt="" />