数据结构与算法总结之递归反转单链表

FantasticPsq

单链表节点的结构：

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x){val = x;}
}

反转整个链表

ListNode reverseLinkedList(ListNode head){
    // base case:只有一个节点就返回那个节点
    if(head.next==null){
        return head;
    }
    ListNode last = reverseLinkedList(head.next);
    // 反转箭头
    head.next.next = head;
    // 头节点的next置空
    head.next = null;
    // 最后一个节点变成头节点
    return last;
}

反转前n个节点

反转前n个节点与反转整个链表的区别是需要记录第n个节点的下一个节点node，然后将head.next设置为node即可。

public class ReverseLinkedList{
    // 记录第n个节点的下一个节点
    ListNoe lastNext = null;
    ListNode reverseFirstN(ListNode head,int N){
    if(N==1){
        lastNext = head.next;
        return head;
    }
    ListNode last = reverseFirstN(head.next,N-1);
    head.next.next = head;
    head.next = lastNext;
    return last;
}
}

反转区间[m,n]部分的链表

1<=m<=n<=链表长度

与反转前n个节点其实是一样的，只是需要找到第m个节点作为递归的头节点，并将第m-1个节点的下一个节点置为last即可。

public class ReverseLinkedList{
    // 记录第n个节点的下一个节点
    ListNoe lastNext = null;
    ListNode reverseBetween(ListNode head,int m,int n){
        if(m==1){
            return reverseFirstN(head,n);
        }
        // ListNode last = reverseBetween(head.next,m-1,n-1);
        // head.next = last;
        head.next = reverseBetween(head.next,m-1,n-1);
    }
}

PengZC

@fantasticpsq 由浅入深挺好

NGU

见解独特，理解深刻

yanrudan

讲的很好呀！