本文最后更新于:10 个月前

单向链表的反转很考验逻辑思维,在面试中经常会被用到,因此是一个必须掌握的知识点。单向链表的反转有很多方法可以处理,这里介绍两种方法:遍历反转法递归反转法

单向链表结构

首先定义结构

public class ListNode {
    //结点的val
    int val;
    //下一个结点
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

问题描述

将单链表数据:1, 2, 3, 4, 5 反转为:5, 4, 3, 2, 1

遍历反转法

  • 从前往后反转各个结点的指针域的指向。

  • 将当前结点curNode的下一个结点 curNode.next 缓存到 temp 后,然后,使当前结点指针指向上一结点 pre

  • 也就是说在反转当前结点指针指向前,先把当前结点的指针域用 tmp 临时保存,以便下一次使用,代码如下:

/**
 * 遍历反转法:从前往后反转各个结点的指针域的指向。
 * @param head
 * @return preNode
 */
public ListNode reverseList(ListNode head) {
    if (head == null) {
        return null;
    }
    // 上一结点
    ListNode preNode = head;
    // 当前结点
    ListNode curNode = head.next;
    // 临时结点,用于保存当前结点的指针域(即下一结点)
    ListNode tmp;
    while (curNode != null) {
        tmp = curNode.next;
        // 反转指向
        curNode.next = preNode;
        // 向下移动
        preNode= curNode;
        curNode = tmp;
    }
    head.next = null;
    return preNode;
}

递归反转法

  • 在反转当前结点之前先反转后续结点。这样从头结点开始,层层深入直到尾结点才开始反转指针域的指向。

  • 就是从尾结点开始,逆向反转各个结点的指针域指向。代码如下:

/**
 * 递归反转法:从尾结点开始,逆向反转各个结点的指针域指向。
 * @param head
 * @return reverseHead
 */
public ListNode reverseListRecur(ListNode head) {
    // head看作是前一结点,head.next 是当前结点,reverseHead是反转后新链表的头结点
    // 若为空链或者当前结点在尾结点,则直接还回
    if (head == null || head.next == null) {
        return head;
    }
    // 先反转后续结点 head.next
    ListNode reverseHead = reverseListRecur(head.next);
    // 将当前结点的指针域指向前一结点
    head.next.next = head;
    // 前一结点的指针域设为null;
    head.next = null;
    // 反转后新链表的头结点
    return reverseHead;
}

代码看起来很简单,实际理解起来却十分烧脑,因此建议你自己在编译器上写一写,打断点去深入理解下。


本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

51.算法实战(三) 上一篇
50.算法实战(二) 下一篇

欢迎关注我的公众号😘