單鏈表反轉(zhuǎn)（java版本）

• 第一種方法
  • 第一步踱葛，判斷節(jié)點是否為空捌锭，節(jié)點是否只有一個
  • 第二步殃饿，設置currentNode記錄為當前結(jié)點饮寞，secondNode記錄下一個節(jié)點孝扛。當前節(jié)點指向為null
  • 第三步，用第三方temp變量將secondNode指向的節(jié)點值保存起來幽崩。將secondNode節(jié)點指向currentNode苦始。重置currentNode為secondNode,重置secondNode為temp。循環(huán)判斷secondNode是否為null
  • 第四步慌申，返回currentNode陌选，即最后一個節(jié)點

private static Node reverseMethodOne(Node node) {
        // 順序依次一個一個反轉(zhuǎn)理郑，設置變量temp記錄變量
        if (node == null)
            return null;
        Node currentNode = node;
        Node secondNode = currentNode.getNext();
        currentNode.setNext(null);
        while (secondNode != null) {
            Node temp = secondNode.getNext();
            secondNode.setNext(currentNode);
            currentNode = secondNode;
            secondNode = temp;
        }
        return currentNode;
    }

• 第二種方法
  • 第一步，判斷節(jié)點是否為空咨油，節(jié)點是否只有一個
  • 第二步您炉，遞歸遍歷，獲取到最后一個節(jié)點役电，依次遞歸回去
  • 第三步赚爵，將當前節(jié)點的下一個節(jié)點指向自己，并將當前結(jié)點指向為null
  • methodTwo 和methodThree相似法瑟。

private static Node reverseMethodTwo(Node node) {
        // 遞歸遍歷鏈表冀膝。知道找到最后一個節(jié)點，并設置其為反轉(zhuǎn)后的新節(jié)點霎挟，不斷遞歸回傳窝剖。
        if (node == null)
            return null;
        if (node.getNext() == null)
            return node;
        Node secondNode = node.getNext();
        node.setNext(null);
        Node reverseHead = reverseMethodTwo(secondNode);
        secondNode.setNext(node);
        return reverseHead;
    }

    private static Node reverseMethodThree(Node node) {
        // 遞歸，區(qū)別于方法2
        if (node == null)
            return null;
        if (node.getNext() == null)
            return node;
        Node reverseNode = reverseMethodThree(node.getNext());
        node.getNext().setNext(node);
        node.setNext(null);
        return reverseNode;
    }

完整代碼

public class N05 {

    /**
     * 鏈表反轉(zhuǎn)
     */
    public static void main(String[] args) {
        Node node1 = new Node("A");
        Node node2 = new Node("B");
        Node node3 = new Node("C");
        Node node4 = new Node("D");
        Node node5 = new Node("E");
        node1.setNext(node2);
        node2.setNext(node3);
        node3.setNext(node4);
        node4.setNext(node5);
        Node newNode = reverseMethodOne(node1);
        print(newNode);
        Node node = reverseMethodThree(newNode);
        print(node);
    }

    private static Node reverseMethodOne(Node node) {
        // 順序依次一個一個反轉(zhuǎn)酥夭，設置變量temp記錄變量
        if (node == null)
            return null;
        Node currentNode = node;
        Node secondNode = currentNode.getNext();
        currentNode.setNext(null);
        while (secondNode != null) {
            Node temp = secondNode.getNext();
            secondNode.setNext(currentNode);
            currentNode = secondNode;
            secondNode = temp;
        }
        return currentNode;
    }

    private static Node reverseMethodTwo(Node node) {
        // 遞歸遍歷鏈表赐纱。知道找到最后一個節(jié)點，并設置其為反轉(zhuǎn)后的新節(jié)點熬北，不斷遞歸回傳疙描。
        if (node == null)
            return null;
        if (node.getNext() == null)
            return node;
        Node secondNode = node.getNext();
        node.setNext(null);
        Node reverseHead = reverseMethodTwo(secondNode);
        secondNode.setNext(node);
        return reverseHead;
    }

    private static Node reverseMethodThree(Node node) {
        // 遞歸，區(qū)別于方法2
        if (node == null)
            return null;
        if (node.getNext() == null)
            return node;
        Node reverseNode = reverseMethodThree(node.getNext());
        node.getNext().setNext(node);
        node.setNext(null);
        return reverseNode;
    }

    private static void print(Node newNode) {
        while (newNode != null) {
            System.out.print(newNode.data + " ");
            newNode = newNode.getNext();
        }
        System.out.println();
    }

}

class Node {
    String data;
    Node next;

    public Node(String data) {
        super();
        this.data = data;
    }

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

    public String getData() {
        return data;
    }

    public void setData(String data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}

參考資料

• 使用遞歸和非遞歸方式反轉(zhuǎn)單向鏈表
• Reversing a linked list in Java, recursively