15 反转链表

题目描述

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

思路1：创建辅助空间 创建一个数组。。翻转一下 或者创建一个栈，先入栈，再出栈。

思路1：创建辅助空间
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;
public class Solution {
    public ListNode ReverseList(ListNode head) {
        
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
       ArrayList a1=new ArrayList();
        ListNode first = head;
        ListNode first1 = head;
        while(first!=null){
            a1.add(first.val);
            first=first.next;
        }
        for(int i=a1.size()-1;i>=0;i--){
            first1.val=(int)a1.get(i);
            first1=first1.next;
        }
        return head;

    }
}

思路2：循环（头插法）

仔细研究了以下思想，最后觉得就是一个很简单的头插法

头插法

要做的事只有一个，首先将头节点L摘下，每遍历一个节点，都以头插法的方式插入以L为头节点的链表中，直到最后一个节点。

LinkList Reverse (LinkList L)
{
　　LNode *p,*r;//p为工作指针，r为p的后继以防断链
　　p=L->next;//从第一个元素结点开始
　　L->next=NULL;//先将头结点L的next域置为NULL
　　while(p!=NULL)//依次将元素结点摘下
　　{
　　    r=p->next;//暂存p的后继
　　    p->next=L->next;//将p结点插入到头结点之后
　　    L->next=p;
　　    p=r;
　　}
　　return L;
}

JAVA 测试代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode L=new ListNode(-1);
        L.next=null;
        ListNode r=null;
        while(head!=null){
            r=head.next;
            head.next=L.next;
            L.next=head;
            head=r;
        }
        return L.next;
    }
}

思路3：递归