反转链表

单链表的反转，我们能想到反转顺序最简单的数据结构就是栈了，如果可以用栈的话，那问题就简单了。顺序遍历单链表，依次入栈直到遍历结束，然后依次出栈重新有前到后连接为一个新的单链表，则自动实现了反转功能。

栈实现

public class Solution {
    public ListNode reverse(ListNode head) {
        //1. 判空处理
        if (head == null || head.next == null){
            return head;
        }

        //2. 遍历链表入栈
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode node = head;
        while (node != null){
            stack.push(node);
            node = node.next;
        }

        //3. 出栈重新建立链表
        ListNode newHead = null;
        ListNode newEnd = null;
        while (!stack.isEmpty()){
            node = stack.pop();
            if (newHead == null){
                newHead = node;
                newEnd = newHead;
                newHead.next = null;
            }else {
                newEnd.next = node;
                newEnd = newEnd.next;
                newEnd.next = null;
            }
        }
        return newHead;
    }
}

遍历实现

原理详解

digraph leetcode_92_1 {

bgcolor="#f7f7f7"

rankdir=LR
subgraph cluster_name {
    subgraph cluster_1 {
        n0 [label="newEnd" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n1 [label="..." shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n2 [label="newHead" shape=circle,color=blue,fillcolor=white,style=filled,width=0.8,fixedsize=true]
        n3 [label="node" shape=circle,color=red,style=dashed,width=0.8,fixedsize=true]
        n4 [label="oldHead" shape=circle,color=blue,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n5 [label="..." shape=circle,color=blue,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        n6 [label="oldEnd" shape=circle,color=blue,fillcolor=lightblue,style=filled,width=0.8,fixedsize=true]
        
        rank=same;
        n0 -> n1 -> n2[dir=back]
        n2 -> n3[style=dashed,color="#f7f7f7"]
        n3 -> n4[style=dashed,color=red]
        n4 -> n5 -> n6
        style=invis
    }

}
label=<<B>图 1.1 遍历反转链表</B>>

}

代码实现

public class Solution {
    public ListNode reverse(ListNode head) {
        //1. 判空处理
        if (head == null || head.next == null) {
            return head;
        }

        //2. 设置反转后新链表表头节点
        ListNode newLinkedListHead = null;

        //3. 设置反转前旧链表表头节点
        ListNode oldLinkedListHead = head;

        //4. 设置临时节点
        ListNode tmpNode = null;

        //5. 遍历旧链表
        while (oldLinkedListHead != null) {
            //5.1 取出当前节点到临时节点
            tmpNode = oldLinkedListHead;

            //5.2 重新设置旧链表表头
            oldLinkedListHead = oldLinkedListHead.next;

            //5.3 把取出的临时节点添加到反转后新链表的表头
            if (newLinkedListHead == null){
                newLinkedListHead = tmpNode;
                newLinkedListHead.next = null;
            }else {
                tmpNode.next = newLinkedListHead;
                newLinkedListHead = tmpNode;
            }
        }
        //6. 返回反转后新链表
        return newLinkedListHead;
    }
}

递归实现

递归实现的原理和栈是类似的，因为递归本身就是利用了程序栈进行了压栈处理，因此好好理解一下第一种算法与第三种算法，有助于理解递归的原理。

public class Solution {
    public ListNode reverse(ListNode head) {
        //1. 判空处理
        if (head == null || head.next == null) {
            return head;
        }

        //2. 获取递归得到的新表头
        ListNode newHead = reverse(head.next);

        //3. 处理当前节点
        head.next.next = head;

        //4. 处理完之后新的尾节点置空
        head.next = null;

        //4. 返回新的表头节点
        return newHead;
    }
}