[每日算法220508] 单链表和双链表的反转

• 链表结构，单链表和双向链表
• 链表的逆序

• 算法要求太严格，理解别人的代码容易。自己写的时候差一点，结果就很难出现。
• 一定要用示例演示算法过程，一开始就写抽象代码，边界条件很难想清楚。
• 算法也是需要背的，多背两遍，多写两边。你就可以说你看这个就是入门的东西。算法并不高级，也不代表聪明程度。大部分人的算法都不到天分的程度。面试基本上也用不到天分。

package linklist;



public class SingleLinkList {
    //单链表结构
    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    //双链表结构
    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int value) {
            this.value = value;
        }
    }





    public static void main(String[] args) {
        DoubleNode d1= new DoubleNode(1);
        DoubleNode d2= new DoubleNode(2);
        DoubleNode d3= new DoubleNode(3);
        d1.last= null;
        d1.next=d2;
        d2.last=d1;
        d2.next=d3;
        d3.last=d2;
        d3.next=null;
        DoubleNode rev = reverseDoubleLinkedList(d1);
        while (rev!=null){
            System.out.println(rev.value);
            rev=rev.next;
        }

    }

    public  static void  testLinkedList(){
        Node node1 = new Node(1);
        node1.next = new Node(2);
        node1.next.next = new Node(3);
        Node rev = reverseLinkedList(node1);
        while (rev != null) {

            System.out.println(rev.value);
            rev = rev.next;

        }
    }

    //传入一个链表，返回逆序的链表
    public static Node reverseLinkedList(Node head) {
        Node pre = null;
        Node next = null;
        //四行代码，顺序一点都不能错
        while (head != null) {//链表最后一个元素的next=null，顺序遍历链表
            next = head.next; //获取下一个元素（不提前保存就被下一步替换了）
            head.next = pre; //第一个元素指向pre时，pre是null
            pre = head;//存储当前元素
            head = next;//head切换下个元素
        }
        return pre;


    }


    //传入一个双链表，返回逆序的双链表
    public static DoubleNode reverseDoubleLinkedList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        //四行代码，顺序一点都不能错
        while (head != null) {//链表最后一个元素的next=null，顺序遍历链表
            next = head.next; //获取下一个元素（不提前保存就被下一步替换了）
            head.last=next;
            head.next = pre; //第一个元素指向pre时，pre是null
            pre = head;//存储当前元素
            head = next;//head切换下个元素
        }
        return pre;


    }


}