单链表反转-阿里云开发者社区

单链表反转

2022-05-14 123

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 今天继续说链表，常见的算法问题有以下几种

前言

今天继续说链表，常见的算法问题有以下几种：

单链表反转
两个有序的链表合并
删除链表倒数第n个结点
求链表的中间结点
链表中环的检测

之前说过链表从尾开始打印链表，有的朋友说和这个单链表反转还是有区别，所以今天就看看这个类似的问题：单链表反转。

题目：单链表反转

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

解法一

题目很简单，就是一个单链表，要求反转链表。

首先一个容易想到的办法就是遍历，每次把指针方向修改:

A —> B 改成 B —> A

但是在修改结点的next之前，必须更新之前的链表指向，否则就无法向后遍历，用图表示下：

public ListNode reverseList(ListNode head) {
        //新链表结点
        ListNode prev = null;
        //临时结点
        ListNode curr = head;
        //开始遍历
        while (curr != null) {
            //先设置一个临时链表结点
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

该算法中，有两个链表：

1、新链表prev，每次改变指向之后要更新链表的结点。

2、旧链表curr，要每次更新到当前结点的next。如上图所示。

开始遍历的时候，先设置一个临时链表结点指向当前结点的next，也就是上图说的情况，先记录下后面要遍历的链表结点。
然后开始反转当前结点指向新链表。
新链表更新到当前结点。
旧链表更新到next。

时间复杂度

由于用到了遍历，所以时间复杂度就是O(n)

空间复杂度

之前说过，链表操作并没有用到另外的n大小空间，只是多了几个类似指针的链表结点,也就是常量空间，操作的还是原来的地址空间，所以空间复杂度为O(1).

解法二

还有个办法就是递归，之前说过只要遇到重复操作并且有终止条件，就可以用到递归。

那我们就先来找找这其中的重复工作。

由刚才的算法得知，从前面开始反转比较麻烦，那我们是不是可以先通过递归递到最后的结点，然后开始往前归呢？

比如先把结点递到最后一个数：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        return p;
    }

这样递归之后，链表结点就来到了最后一个结点，然后开始往回归，也就是把每个结点的链表反转。

假如 A -> B，我们需要反转这两个结点，你能想到什么办法呢？

很简单：

B.next=A

那B是怎么算出来的呢？

A.next=B
B.next=A 
==>
A.next.next=A

反转的方法找到了，这也就是我们需要做的重复工作：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        return p;
    }

但是还少了点啥？链表尾结点必须指向null，所以我们还需要再重复工作中加上在反转两个结点之后，再指向null的工作。

所以最后的算法就是：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }