单向链表的反转

单链表的反转有三种实现方法

    遍历法（结构清晰易懂，时间复杂度低）
    递归法（代码简洁，但时间复杂度高，尤其是在链表长度超过12000之后）
    内置类法（代码简洁，使用内置LinkedList类）


1.遍历法（关键代码）

    static Node reverse(Node head) {
        if(head == null){
            return null;
        }
        Node pre = null;
        Node cur = head;
        Node reHead = null;
        
        //如果当前结点为空，结束循环
        while (cur != null) {
            //保存下一个结点，以免丢失
            Node temp = cur.next;
            //1.对pre和cur结点的关系进行反转。本来是pre指向cur的，用下面这条代码能够把cur指向pre。
            cur.next = pre;
            
            //2.如果下一个结点为空，那他就是反转链表的头结点
            if (temp == null) {
                reHead = cur;
            }
            
            //3.上一个结点已经反转完成啦！现在要移动到下一个结点了！
            pre = cur;
            cur = temp;
        }
        return reHead;
    }

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26

上面方式的化简版，代码简短，但是没那么容易理解

static Node reverse(Node head) {
    Node pre = null;
    Node temp = null;

    while(head != null){
        //1.记录下一个结点
        //2.指针反转
        temp = head.next;
        head.next = pre;

        //3.光标移向原链表的下一个结点
        pre = head;
        head = temp;
    }

    return pre;
}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18


2.递归法（关键代码）

static Node reverse(Node head) {
    //我们从原链表的头结点开始
    Node cur = head;
    //递归到原链表的尾结点结束。递归到了尾结点的时候，就返回当前结点。
    if (cur == null || cur.next == null) {
        return cur;
    } else {
        Node reHead = reverse(cur.next);
        cur.next.next = cur;
        cur.next = null;
        return reHead;
    }
}

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13


3.内置类法

LinkedList没有提供反转链表的相关函数，以下是通过foreach实现链表反转
static LinkedList reverse(LinkedList linkedList) {
    LinkedList<Object> newLinkedList = new LinkedList<>();
    for (Object object : linkedList) {
        newLinkedList.add(0, object);
    }
    return newLinkedList;
}

———————
作者：RunFromHere
来源：CSDN
原文：https://blog.csdn.net/baidu_/article/details/
版权声明：本文为博主原创文章，转载请附上博文链接！

讯享网