##題目

給定一個鏈表head，要求反轉(zhuǎn)這個鏈表

鏈表節(jié)點定義如下

package com.dai.common;

public class Node {
    public Integer value;
    public Node next;

    public Node() {
    }

    public Node(Integer value) {
        this.value = value;
    }

    public Node(Integer value, Node next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        Node temp = this;
        StringBuilder str = new StringBuilder();
        while (temp != null) {
            str.append(temp.value).append("->");
            temp = temp.next;
        }
        str.append("null");
        return str.toString();
    }
}

##解題思路

首先先考慮極端情況

第一種情況

當鏈表為null或者只有一個節(jié)點的時候

不存在反轉(zhuǎn)的情況，直接返回就行

第二種情況

當鏈表有兩個節(jié)點的時候

也就是head.next.next=null的時候

也很簡單，定義兩個pre和cur

分別指向第一個和第二個節(jié)點

然后令pre.next指向空，cur.next指向pre

此時，cur就是反轉(zhuǎn)之后的鏈表了

第三種情況

當鏈表的節(jié)點數(shù)為3的時候呢？

可以采用整體法的思路

在第二種情況的基礎上，將前兩個節(jié)點看成一個整體，當作一個節(jié)點

此時pre還是指向的“第一個節(jié)點”，cur還是指向的第二個節(jié)點

那這樣問題就簡單了，還是采用第二種情況的方式反轉(zhuǎn)鏈表就行了

依此類推

只需要搞定前兩種情況

剩下的情況放到一個循環(huán)中做一樣的處理就行

##算法圖解

如下圖是一個擁有八個節(jié)點的鏈表

圖片

為了方便理解，我們cur.next也作為一個單獨的指針定義出來

此時可以將pre指向第一個節(jié)點

cur指向第二個節(jié)點

因為第一個節(jié)點在反轉(zhuǎn)后是需要指向null的

所以此時pre.next=null

圖片

接著判斷一下cur是否為null

不為null則需要將cur.next指向pre

因為第二個節(jié)點指向第一個節(jié)點之后

后續(xù)的節(jié)點就無法拿到了，所以需要先將next指向第三個節(jié)點

圖片

然后將cur.next指向pre

圖片

然后將pre=cur

圖片

令cur=next，指向第三個節(jié)點

** 注意觀察 ！**

此時如果將pre指向的鏈表看做一個節(jié)點

是不是又回到了最初的狀態(tài)？

圖片

同樣的方法進行pre、cur、next指針的變動

只要cur或者next不為null，就可以一直走下去

圖片

圖片

直到最后，cur或者next為null

鏈表也反轉(zhuǎn)完成了

pre指向的鏈表就是反轉(zhuǎn)后的鏈表啦！

圖片

##代碼實現(xiàn)

package com.dai.code;

import com.dai.common.Node;

public class ReverseLinkedList1 {

    public static Node reverseLinkedList(Node head) {
        // 當鏈表為空，或者長度為1的時候走這里
        if (null == head || null == head.next) {
            return head;
        }
        // 當鏈表只有兩個節(jié)點的時候
        Node pre = head;
        Node cur = head.next;
        Node next = cur;
        pre.next = null;

        // 當鏈表有三個及以上節(jié)點的時候
        while (next != null) {
            next = next.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }
}

測試一下

public class ReverseLinkedList1 {
    public static void main(String[] args) {
        Node head = new Node(1);
        Node temp = head;
        for (int i = 2; i < 10; i++) {
            temp.next = new Node(i);
            temp = temp.next;
        }
        System.out.println(head + "：：反轉(zhuǎn)：：" + reverseLinkedList(head));
    }
}

圖片

文/戴先生@2021年11月19日

---end---

更多精彩推薦