一个node链表翻转的面试题

经典面试题总结,欢迎大家来留言区讨论

下面列举了两种解法:
欢迎留言讨论
一个node链表的值分别为67,0,24,58,31,请把node翻转

public static class Node {
    int val;
    Node next = null;
    Node(int val) {
        this.val = val;
    }
}

public static void main(String[] args) {
    Node nodeFirst = new Node(67);
    nodeFirst.next = new Node(0);
    nodeFirst.next.next = new Node(24);
    nodeFirst.next.next.next = new Node(58);
    nodeFirst.next.next.next.next = new Node(31);

    Node node = reverseNodeByNodeMethod(nodeFirst);
    while (node != null) {
        System.out.println(node.val);
        node = node.next;
    }
}

一种利用node自身的方法翻转.

public static Node reverseNodeByNodeMethod(Node nodeFirst) {
    Node currentNode = nodeFirst;
    Node nextNode = null;
    Node nextNextNode;
    Node newFirstNode = null;
    if (currentNode.next != null) {
        nextNode = currentNode.next;
    }
    currentNode.next = null;
    while (nextNode != null) {
        if (nextNode.next != null) {
            nextNextNode = nextNode.next;
        } else {
            newFirstNode = nextNode;
            nextNode.next = currentNode;
            break;
        }
        nextNode.next = currentNode;
        currentNode = nextNode;
        nextNode = nextNextNode;
    }
    return newFirstNode;
}

第二种解法,将node所有节点放入stack中,为了防止造成node内部循环,所以在stack存储之后将node.next置为null

public static Node reverseNodeByStack(Node nodeFirst) {
    Stack<Node> stack = new Stack<>();
    Node node = nodeFirst;
    while (node.next != null) {
        Node nextNode = node.next;
        stack.push(node);
        node.next = null;
        node = nextNode;
    }
    Node newFirstNode = node;
    while (!stack.isEmpty()) {
        node.next = stack.pop();
        node = node.next;
    }
    node.next = null;
    return newFirstNode;
}