初学算法的小菜鸡 - 自学笔记 (第十一天): 链表相关算法(一) 反转链表Leetcode 206题

Leetcode题目链接t

题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 

示例1:

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2:

输入：head = [1,2]
输出：[2,1]

示例3:

输入：head = []
输出：[]

不计内存代价暴力解法

通常能够想到的最直接进行反转链表的方法就是重新创建一个新的链表从而完成反转的操作，而且题目中也没有限制其空间复杂度为O(1)。

因此代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        int size = 0;
        if(cur == null){
            return head;
        }
        //获取链表长度size
        while(cur != null){
            cur = cur.next;
            size++;
        }
        //建立新的数组存储链表数值，利用已获取的size
        int[] valList = new int[size];
        int index = 0;
        while(head != null){
            valList[index] = head.val;
            index++;
            head = head.next;
        }
        //创建新链表，将数组中的值反向加入链表中
        ListNode new_temp_head = new ListNode(valList[index-1]);
        cur = new_temp_head;
        for (int i = index-2; i>=0;i--){
            ListNode new_temp_node = new ListNode(valList[i]);
            cur.next = new_temp_node;
            cur = cur.next;
        }
        return new_temp_head;

        }
}

结果如下：

写这种暴力解法时已经尽量避免时间复杂度过高， 从空间复杂度来说本解法确实消耗内存巨大。在使用这种解法时由于额外创建了一个数组和一个新链表，因此空间复杂度为O(2n)。

事实上只需要使用我们之前在数组中熟悉的技巧就能够将空间复杂度降低为O(1)。

双指针法

事实上我们只需要将每个节点的next指针转个向就可以完成整个反转过程。在这个指针转向的过程中需要知道当前节点和上一个节点，因此双指针法就再适合不过了。

 整个反转过程如图，单列表只能从头向尾移动，因此我们在进行指针转向时还要记得原来的头节点在转向后指向Null。因此就有了如下代码：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null){
            temp = cur.next;
            cur.next = prev;
            prev = cur;
            cur = temp;
        } 
        return prev;
        }
}

 执行结果如下：

 能够看到这个内存的消耗确实是减少了，但是我依然还是觉得内存消耗的减少并不明显。但从空间复杂度上将这种写法已经将空间复杂度从O(2n)降为了O(1)。

理解了双指针法我们就可以在对写法进行进一步优化，将双指针的过程改写为递归结构。

递归法

递归法的原理和双指针法是相同的。

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}

反转列表就到此为止了，也欢迎各位大神在评论区提出批评指正或者留下您自己的写法，编写不易希望看到的小伙伴们能够给予点赞和关注的支持。您的支持将会是我继续写下去的动力！！！