2025年c++单向链表反转（4种算法,实现单链表的反转!）

编程日记 • 2025-01-28 14:51 • 阅读 37

单向链表的反转

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

    遍历法（结构清晰易懂，时间复杂度低）
    递归法（代码简洁，但时间复杂度高，尤其是在链表长度超过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_34122324/article/details/82850861
版权声明：本文为博主原创文章，转载请附上博文链接！

2025年c++单向链表反转（4种算法,实现单链表的反转!）

相关推荐