面試題: 怎麼将單連結清單反轉？

        反轉連結清單這是在面試中經常會被遇到的一個與連結清單相關的問題，我也被問到過。

        第一反應想到就是讓連結清單反轉，那還不簡單，加一個棧不就行了。面試官搖了搖頭，說能不用棧嘛，用棧的空間複雜度是o(n), 其實不用額外空間也可以實作。

        經過一番引導後，我想到了通過反轉指針的方式，但是當時并沒有寫出完整的代碼，在此彌補面試的空缺。

        實作思路: 

        1) 新增一個pre指針，指派為null。用來記錄每次循環後結果。

        2) 從head節點開始周遊連結清單，暫存目前head節點，以免在指派給pre時之前的head節點由于移到下一個節點時被修改。

Node current=head;
head=head.next;
           

        3)  斷掉目前節點指向下一個節點的指針，即反轉指針。 實作目前節點指向上一次循環時的節點（超過一個節點就是一個連結清單），第一次循環時pre=null。

          current.next=pre。
           

        4)  pre 鍊增長。将之前的head節點指派給pre。

pre=current。
           

完整代碼: 

package chain;

/**
 * @author bingbing
 * @date 2021/5/25 0025 22:13
 */
public class ReverseList {

    static class Node {
        Object data;
        Node next;

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }


    public static void main(String[] args) {
        Node node5 = new Node(5, null);
        Node node4 = new Node(4, node5);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node head = new Node(1, node2);
        Node res = reverse(head);
        Node next = res.next;
        System.out.print(res.data + "->");
        while (next != null) {
            System.out.print(next.data + "->");
            next = next.next;
        }
        System.out.print("NULL");
        System.out.println("");
    }

    /**
     * 反轉連結清單
     *
     * @param head
     * @return
     */
    public static Node reverse(Node head) {
        Node pre = null;
        while (head != null) {
            Node current = head;
            head = head.next;
            current.next = pre;
            pre = current;
        }
        return pre;
    }

}
           

列印結果: