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

版权声明：本文为博主原创文章，转载请注明出处：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);
    }
}

递归解法进阶版

public ListNode ReverseList(ListNode head) {
    if(head == null) return null;
    if(head.next == null) return head;
    ListNode node = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return node;
}