优雅的反转链表 优雅的反转链表情包

一、思路

1. 非递归。

1）不用栈。重复将首节点的下一个节点调整到最前面，如链表1->2->3->4，调整过程为2->1->3->4，3->2->1->4，4->3->2->1

2）使用栈。栈先进后出。将原链表的元素从头到尾入栈后，从栈顶到栈底的元素的顺序即为原链表反转后的顺序。

2. 递归。使链表从尾节点开始指向前一个节点。

二、代码

public class Solution {
    //节点类
    public static class Node {
        //当value值为-1时，代表是虚拟头结点
        int value;
        Node next = null;
        Node(int value) {
            this.value = value;
        }
    }


    /**
     *  构建链表（递归）
     * @param list  内容即是要构建的链表含有的元素
     * @return 与list相同顺序的链表
     */
    public static Node constructNodeListRecursive(List<Integer> list){
        if (list.isEmpty()){
            return null;
        }
        Node headNode = new Node(list.get(0));
//        子递归构建链表
        Node tempNode = constructNodeListRecursive(list.subList(1, list.size()));
//        头结点指向子递归构建的链表头部
        headNode.next=tempNode;
        return headNode;
    }

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);

//        调用非递归方法（不用栈）
        Node nodeList1 = constructNodeListRecursive(list);
        Node resultNonRecursive = reverseLinkedListNonRecursive(nodeList1);
//        输出结果
        dump(resultNonRecursive);

        //        调用非递归方法（使用栈）
        Node nodeList2 = constructNodeListRecursive(list);
        Node resultRecursiveStack=reverseLinkedListNonRecursiveStack(nodeList2);
//        输出结果
        dump(resultRecursiveStack);


//        调用递归方法
        Node nodeList3 = constructNodeListRecursive(list);
        Node resultRecursive=reverseLinkedListRecursive(nodeList3);
//        输出结果
        dump(resultRecursive);

    }
//    输出结果
    public static void dump(Node head) {
        if (null != head) {
            Node temp=head;
            while (null!=temp){
                System.out.print(temp.value);
                System.out.print(" ");
                temp=temp.next;
            }
            System.out.println();
        }

    }


    /**
     * 非递归方法，不用栈
     * @param head  头结点
     * @return 链表反转过后的头结点
     */
    public static Node reverseLinkedListNonRecursive(Node head){
        if (head == null || head.next == null){
            return head;
        }
        //构建一个虚拟头节点，用于翻转链表操作
        Node p = new Node(-1);
        p.next = head;
        Node nextNode = head.next;
        while (nextNode != null){
            //后一个节点调整到前面
            head.next = nextNode.next;
            nextNode.next = p.next;
            p.next = nextNode;
            nextNode = head.next;
        }
        return p.next;
    }

    /**
     * 非递归方法，使用栈（栈先进后出，天生就可以反转链表）
     * @param head  头结点
     * @return 链表反转过后的头结点
     */
    public static Node reverseLinkedListNonRecursiveStack(Node head){
        Stack<Node> nodeStack = new Stack<>();
        Node temp = null;
        //从头结点开始存入栈中
        while (head != null){
            nodeStack.push(head);
            head = head.next;
        }
        //栈顶的元素即为链表原来的最后一个元素
        if ((!nodeStack.isEmpty())){
            temp = nodeStack.pop();
        }
        //栈中元素依次处理
        while (!nodeStack.isEmpty()){
            Node tempNode = nodeStack.pop();
            tempNode.next.next=tempNode;
            tempNode.next=null;
        }
        return temp;
    }


    /**
     * 递归方法
     * @param head  头结点
     * @return 链表反转过后的头结点
     */
    public static Node reverseLinkedListRecursive(Node head) {
//        子递归结束
        if (head == null || head.next == null) {
            return head;
        }
//        获取去除头结点之外的链表反转后的头结点
        Node pNode = reverseLinkedListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return pNode;
    }
}

致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。