反转链表专题

No.1 问题描述

输入一个链表，从尾到头的顺序返回一个ArrayList

解题思路

1.使用递归法

//1.解法一
public ArrayList<Integer> printListReverse(ListNode listnode){
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    if(listnode != null){
        arrayList.addAll(printListReverse(listnode.next));
        arrayList.add(listnode.val);
        }
    return arrayList;
}
//分析：时间复杂度为O（n）,相当于将每个元素均遍历了一遍
//空间复杂度为O（n^2）,创建的列表的合计元素个数1+2+3+4+n-1
//拓展内容：ArrayList中的addAll(Collection<? extends E> c) 方法 按照指定collection容器返回元素的
//顺序将所有的元素添加到列表的尾部

2.使用栈（推荐解法）

//Java实现
public ArrayList<Integer> printListReverse(ListNode listnode){
    ArrayDeque<Integer> stack = ArrayDeque<Integer>();
    while(listnode != null){
        stack.addFirst(listnode.val);
        listnode = listnode.next;
    }
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    while(stack.pollFirst())
        arrayList.add(stack.pollFirst())
    return arrayList;
}
//Java中推荐使用ArrayDeque来实现一个栈
//当压栈时，调用addFirst()方法; 出栈时调用pollFirst()方法
//分析：时间复杂度O(n)，空间复杂度也是O（n）

#基于Python的实现
class Solution:
    def printListReverse(self,listnode):
        if not listnode:
            return []
        result = []
        while listnode:
            result.insert(0,listnode.val)
            listnode = listnode.next
        return result;
#Python中推荐使用list列表来实现堆栈
#空间复杂度为O（n）,时间复杂度为O（n^2）

其实在Java的实现中实际的空间复杂度为O（2n），Python中的空间复杂度为O（n）；但是Python中

当向列表的头部插入元素时，时间复杂度为O（n），总共为O（n^2），所以可以看出Java实现中是以多出

O(n)的空间复杂度换取时间复杂度的降低

3.使用头插法

创建单链表的方法有两种，分别是头插法和尾插法

头插法就是按节点的逆序方法逐渐将节点插入到链表的头部，尾插法就是按照节点的顺序逐渐将节点插入

到链表的尾部；头插法创建的链表是逆序的，这也正符合本题中的要求

头插法的算法描述：从一个空表开始，重复读入数据，生成新节点，将读入数据存放到新结点的数据域中

然后将新结点插入到当前链表的表头节点之后

1xa7VJ.jpg

尾插法是从一个空表开始，重复读入数据，生成新节点，将读入数据存放到新节点的数据域中，然后将

新节点插入到当前的末尾节点之后

1xab5R.jpg

//Java使用头插法构建逆序链表
public ArrayList<Integer> printListReverse(ListNode listnode){
    ListNode head = new ListNode(-1);
    while(listNode != null){
        ListNode newNode = listnode.next;
        listnode.next = head.next
        head.next = listnode;
        listnode = newNode;
    }
    //构建ArrayList
    ArrayList<Integer> arrayList = new ArrayList<Integer>();
    head = head.next;
    while(head!=null){
        arrayList.add(head.val);
        head = head.next;
    }
    return arrayList;
}
//分析：时间复杂度为O（n）,空间复杂度也是O（n）

No.2 问题描述

反转一个链表、反转一个链表的前N个元素、反转一个链表的部分元素

//递归实现单链表的反转 代码实现
//输入一个节点head,将以head为起点的链表反转，并返回反转之后的头节点
public ListNode reverse(ListNode head){
    if(head == null) return head;
    if(head.next == null) return head;  //链表只有一个节点时，反转也只是它自己
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

//递归实现反转一个链表的一部分
private ListNode successor = null;   //后驱节点
public ListNode reverseN(ListNode head, int n){
    if(n==1){
        successor = head.next;
        return head;
    }
    ListNode last = reverseN(head.next,n-1);
    //让反转之后的节点和后面的节点连接起来
    head.next.next = head;
    head.next = successor;
    return last;
}

public ListNode reverseBetween(ListNode head,int m,int n){
    if(m == 1){
        return reverseN(head,n);
    }
    //将反转后的头结点赋值成当前节点的下个节点
    head.next = reverseBetween(head.next,m-1,n-1);
    return head;
}