反转单链表（java）

客官°小女子只卖身不卖艺 2022-05-13 10:04 220阅读 0赞

> 反转单链表：输入链表头节点，输入反转后的链表头节点

**第一次想到的解法（时间和空间复杂度较高）**

> 将单链表每个节点依次读入到栈中，然后出栈，重新连接成反转后的单链表

public static ListNode convert(ListNode node) {
    
            if (node == null) {
                return null;
            }
            Stack<ListNode> stack = new Stack<>();
            //入栈
            while (node != null) {
                stack.push(node);
                node = node.next;
            }
    
            ListNode header = stack.pop();
            ListNode current = header;
            ListNode next;
            while (!stack.isEmpty()) {
                next = stack.pop();
                current.next = next;
                current = current.next;
            }
            return header;
        }

**快速解法，通过更改链表节点的指针（引用）来直接反转**

public static ListNode fastConvert(ListNode node) {
    
            if (node == null) {
                return null;
            }
    
            //前一个节点
            ListNode pre = null;
            //当前节点
            ListNode current = node;
            //下一个节点
            ListNode next;
    
            //新的头节点
            ListNode header = null;
            while (current != null) {
                //当前节点的下一个
                next = current.next;
                //当前节点为最后一个，则该节点为新的表头
                if (next == null) {
                    header = current;
                }
                //当前节点前节点变成后节点
                current.next = pre;
                //前一个节点后移
                pre = current;
                //当前节点后移
                current = next;
    
            }
            return header;
        }