数据结构-单链表反转的三种方式

单链表是一种线性数据结构，由当前节点数据和指向下个节点的指针组成，因为是单向的，所以称为单链表

单链表的反转：

例如：1—>2—>3—>4 反转成：4—>3—>2—>1

首先定义一个链表的节点：

public class Node {
    private int data;
    private Node next;

    public Node(int data) {
        this.data = data;
        next = null;
    }
    //添加节点
    public Node addNode(Node node) {
        next = node;
        return node;
    }

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

    public Node getNext() {
        return next;
    }

   @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                ‘}‘;
    }
}

方式一：遍历节点，反转每个节点，也叫头插法，因为节点依次插入了新链表的头部

因为单链表只有指向下一个节点的指针，没有指向上个节点的指针。所以我们可以定义个指针指向上个节点，这样我们遍历链表，把每个指向下个节点的指针，指向上个节点，这样每个节点都指向了上个节点，实现了反转。如下图所示：

preNode 指向上个节点，curNode指向当前节点，让curNode的next指向preNode,然后移动preNode 和 curNode ，这样最终以preNode为头结点，实现了单链表的反转

代码：

public Node reverse() {
        if (this == null || this.next == null) {
            return this;
        }
        //上个节点
        Node preNode = null;
        //当前节点
        Node curNode = this;
        while (curNode != null) {
            //当前节点的下个节点
            Node next = curNode.getNext();
            //修改当前节点的下个节点，让其指向上个节点
            curNode.setNext(preNode);
            //上个节点移动到当前节点
            preNode = curNode;
            //当前节点移动到下个节点
            curNode = next;
        }
        return preNode;
}

测试：

public class Test {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.addNode(new Node(2)).addNode(new Node(3));
        System.out.println("反转前：" + head);
        Node reverse = head.reverse();
        System.out.println("反转后：" + reverse);
    }
}
结果：
反转前：Node{data=1, next=Node{data=2, next=Node{data=3, next=null}}}
反转后：Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}

方式二：借助栈的特性，先进后出，实现单链表的反转

public static Node reverse2(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Stack<Node> stack = new Stack<>();
        while (head != null) {
            stack.push(head);
            head = head.getNext();
        }
        head = stack.pop();
        //当前节点的位置
        Node cur = head;
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            node.next = null;
            cur.next = node;
            cur = node;
        }
        return head;
}

方式三：递归

递归的方式理解起来，感觉有点困难

public static Node reverse3(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node prev = reverse3(head.next);
        head.next.next = head;
        head.next = null;
        return prev;
}

测试

public class Test {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.addNode(new Node(2)).addNode(new Node(3));
        System.out.println("反转前：" + head);
        Node reverse = Node.reverse3(head);
        System.out.println("反转后：" + reverse);
    }
}
结果：
反转前：Node{data=1, next=Node{data=2, next=Node{data=3, next=null}}}
反转后：Node{data=3, next=Node{data=2, next=Node{data=1, next=null}}}

数据结构-单链表反转的三种方式

原文：https://www.cnblogs.com/lichlaughing/p/13855630.html