【算法】反转链表——递归解法

版权声明:本文为博主原创文章,转载请注明出处:https://twocups.cn/index.php/2020/01/16/14/

最近我遇到了“反转链表”这道算法题,发现用递归解的人很少(LeetCode的官方答案中就有用递归解的,但那个答案不太好理解)。其实递归思想真的非常适合解决单向链表的题目,因为对单向链表使用递归时,相当于能反向遍历一遍链表,使单向链表具备双向链表的属性。这里是提供一种递归解法的思路,不是说递归解法是最好的。

题目描述

输入一个链表,反转链表后,输出新链表的表头。

链表结构

public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

交换位置解法

public ListNode ReverseList(ListNode head) {
    if(head==null)
        return null;
    ListNode newHead = null;
    ListNode pNode = head;
    ListNode pPrev = null;
    while(pNode!=null){
        ListNode pNext = pNode.next;
        if(pNext==null)
            newHead = pNode;
        pNode.next = pPrev;
        pPrev = pNode;
        pNode = pNext;
    }
    return newHead;
}

递归解法

ListNode newln,p;
public ListNode ReverseList(ListNode head) {
    this.tempReverseList(head,-1,false);
    return newln;
}
void tempReverseList(ListNode head,int val,boolean b){
    if(head !=null){
        this.tempReverseList(head.next,head.val,true);
        if(b == true){
            p.next = new ListNode(val);
            p = p.next;
        }
    }else{
        if(b == true) p = newln = new ListNode(val);
    }
}

相关文章

【算法】链表中倒数第k个结点——递归解法

【算法】十大排序算法总结(Java代码实现)

2 条评论

请到【后台 - 用户 - 我的个人资料】中填写个人说明。

2 条评论

sky

“this.tempReverseList(head,-1,false);”
有点没看懂,这个-1和false是干什么用的?

回复

林皓伟

@sky 设置“-1”和“false”的目的是相同的——为了让新生成的链表在正确的地方停止。
这个算法最核心的特点,就是利用递归来在当前链表结点获得前一个链表结点的值,这样就可以“逆序”遍历整个单向链表了。
那么问题来了,如果当前位置在原链表的表头会出现什么状况呢?
一个值为“-1”的链表结点将被生成,然后由于判断位“false”而不被加入新的链表,这样新链表就在正确的地方停止了。
其实,“-1”改成“-2”也可以,这只是占位置的,并且在我出错的时候可以明显地提醒我出错的地方。

回复

发表评论