关于线性表等相关概念请点击这里。
目前,可以有两种方法实现该要求。
方法一:借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。此处,可理解为将链表装换为顺序表,然后把队伍方向反转,但是,此方式比较浪费空间,而且需要两次遍历,效率不占优势。
代码实现:
public static Node ReverseList1(Node head)
{
//指针是否为空判断(鲁棒性)
if(head == null)
{
return null;
}
//定义新的链表nodeList
List<Node> nodeList = new List<Node>();
//当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;
}
}
当然,用递归也能实现哦。该题鲁棒判断在于指针是否为空。