题目描述

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

一 . 概念普及

        关于线性表等相关概念请点击。

二 . 实现方法

        目前，可以有两种方法实现该要求。

        方法一：借助外部空间实现。这里可以将单链表储存为数组，然后按照数组的索引逆序进行反转。此处，可理解为将链表装换为顺序表，然后把队伍方向反转，但是，此方式比较浪费空间，而且需要两次遍历，效率不占优势。

        代码实现：

public static Node ReverseList1(Node head)    {         //指针是否为空判断（鲁棒性）        if(head == null)        {            return null;        }         //定义新的链表nodeList        List
      
        nodeList = new List
       
        ();        //当head不为空时，执行        while (head != null)        {            nodeList.Add(head);            head = head.Next;        }        //        int startIndex = nodeList.Count - 1;        for (int i = startIndex; i >= 0; i--)        {            Node node = nodeList[i];            if (i == 0)            {                node.Next = null;            }            else            {                node.Next = nodeList[i - 1];            }        }        // 现在头结点是原来的尾节点        head = nodeList[startIndex];        return head;    }
       
      

        方法二：三指针法，不做过多阐述，代码备注蛮详细的。下图即为具体实现过程。

        代码实现：

class Solution{    public ListNode ReverseList(ListNode pHead)    {        // write code here        //鲁棒判定        if(pHead == null)        {            return null;        }        //定义A B 两个指针        ListNode A = null;        ListNode B = null;        //循环操作        while(pHead != null)        {            //定义B为PHead后面的数，定义A为pHead前面的数            B = pHead.next;            pHead.next = A;  //这一部分就理解成A是PHead前面的那个数吧。            //然后再把A和pHead都提前一位            A = pHead;            pHead = B;        }        //循环结束后，返回新的表头，即原来表头的最后一个数。        return A;    }}

        当然，用递归也能实现哦。该题鲁棒判断在于指针是否为空。