Leetcode206.反转链表

1.题目描述

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

2.解答

首先我的思路就是头插法,但是写出来的代码确实超出时间限制,我整个人都傻了,难道头插法不是反转单链表的一个经典解法嘛,由于太复杂超时了?然后我就刚了起来,把代码贴到IDEA中自己写测试用例,通过使用IDE的debug发现了问题,刚开始多加了一个条件判断,我写出的代码是这样的:

ListNode temp = head;
while(temp != null){
    if(newHead.next == null){
        newHead.next = temp;
        temp = temp.next;
    }
}

第一次进行判断的时候,newHead为只有一个头节点的空链表,如图:

电脑上面的画图我是真的不会,原谅我

在第二次temp指向2的时候,进行插入之后是这样的:

那么这时这条划红线的指针就出问题了,后面的节点可以保证顺序,但是当遍历到1的时候就会出现死循环

那么最终的解决方法就是直接去掉这个条件判断:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)    return null;
        ListNode newHead = new ListNode(0);
        ListNode temp = head;
        ListNode p = null;
        while(temp != null){
            p = temp.next;
            temp.next = newHead.next;
            newHead.next = temp;
            temp = p;
        }
        return newHead.next;
    }
}

当newHead.next为空时,直接temp.next = newHead.next == null就可以解决问题

收获:

解题时各种边界条件先依次给出,最后检查各个边界条件是否可以合并,是否可以省掉一些


第二种方法是使用递归,思路上还是比正向直接来要难一些的,不过不熟才要练嘛,要敢于走出自己的舒适区

刚开始我的递归条件写成了这个样子:

public ListNode reverseList(ListNode head) {
    ...
    if(head.next != null){
        ListNode res = reverseList(head.next);
        res.next = head;
        return head;
    }
    else{
        return head;
    }
    ...
}

当前链表为:1-2-3-4-5

这种方法虽然能实现将链表所有的指针反过来,但是不能将反转之后的头节点,也就是5返回,这种方法每次返回的都是用来操作的节点,而不是结果节点,例如当节点4调用返回时,返回的是4,当节点3获取到返回值时,直接使用res.next = head,但是这样虽然反转了链表,但是根本获取不到,最终最外一层返回了一个头节点,有什么用呢?这只是反转之后的最后一个节点,接下来修改为直接返回结果值:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private ListNode newHead = new ListNode(0);
    public ListNode reverseList(ListNode head) {
        //为了良好的编程习惯,在程序完成之后需要检查是否有可以合并的条件,例如下面这样,将判断条件和递归终止条件直接何为一个,棒~~~
        if(head == null || head.next == null)    return head;                
           ListNode res = reverseList(head.next);
           head.next.next = head;
           head.next = null;
           return res;              
    }
}

除了头插法和递归以外,这里还有一种迭代方法,就是在遍历链表的过程中,将链表进行反转

需要使用prev节点来记录前一个位置,还需要使用next节点来记录下一个位置,这样在当前节点修改next指针之后,通过curr = next才能找到下一个节点的位置进行继续遍历,这个方法也是挺好的

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null)    return head;
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        while(curr != null){
             next = curr.next;
             curr.next = prev;
             prev = curr;
             curr = next;             
        }
        return prev;
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode206反转链表md