1.题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000

2.问题分析

其实倒不是很难，我们只需要两遍遍历即可，第一遍遍历把链表中所有信息域存入数组，下标为0存储第一个结点的数据域，下标为1的存储第二个结点的数据域，依次类推。第二遍遍历我们从头结点开始，头结点的数据域换成数组最后一个位置的数据，把第二个结点的数据换成数组倒数第二个位置的数据，这样就实现了链表的倒置

3.代码实现

3.1C++代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
       ListNode* cur=head;
       int arr[5005];//存放链表数据域
       int cnt=0;//用于记录数组个数
       while(cur)//第一次遍历
       {
          arr[cnt++]=cur->val;
          cur=cur->next;
       }
       cur=head;
       while(cur)//第二次遍历
       {
           cur->val=arr[--cnt];
           cur=cur->next;
       }
       return head;
    }
};

3.2Java代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur=head;
       int arr[]=new int[50005];
       int cnt=0;
       while(cur!=null)
       {
          arr[cnt++]=cur.val;
          cur=cur.next;
       }
       cur=head;
       while(cur!=null)
       {
           cur.val=arr[--cnt];
           cur=cur.next;
       }
       return head;
    }
}