反转链表
考点：链表
题目描述
输入一个链表，反转链表后，输出新链表的表头。
代码格式
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
}
}
image.png
解题一—递归
1.思路
假设链表为[1,2,3,4,5]先迭代到链表末尾5，然后从5开始依次反转整个链表
如下图所示，先迭代待最后一位5，并且设置一个新的节点newList作为反转后链表的头结点，由于整个链表反转后的头就是最后一个数，所以newList存放的一直是反转后的头结点的地址，将head指向的地址赋值给head->next->next指针，并且一定要记得让head->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层head->next->next赋值的时候会覆盖后续的值。依次反转。。
image.png
2.代码
/*
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||head.next==null){
return head;
}
ListNode newList = ReverseList(head.next); //一直循环到链尾
head.next.next = head; //翻转链表的指向
head.next = null; //记得赋值NULL，防止链表错乱
return newList; //新链表头永远指向的是原链表的链尾
}
}
解题二—非递归-改变指针的位置
1.思路
（1） 题目所给的是单链表，反转后的链表应该为：最后一个结点指向倒数第二个，倒数第二个指向倒数第三个，......，第二个指向第一个，第一个指向null;
（2）知道了反转后各个结点指向哪之后，就需要开始调整每个结点的next指针。
（3）这就需要把结点挨个从链表上摘下来，做调整；
（4） 这个调整过程需要两个指针辅助：pre记录其前一个结点位置，好让该结点的next指针指向前一个结点，但是在指向前一个结点前需要用一个指针next记录后一个结点地址，避免结点丢失。
-
以3个节点为例：
pre指针，用于记录当前结点的前一个结点地址
next指针，用于记录当前结点的下一个结点地址
image.png
2.代码
/*
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||head.next==null){
return head;
}
ListNode pre=null;//初始化pre指针，用于记录当前结点的前一个结点地址
ListNode next=null; //初始化next指针，用于记录当前结点的下一个结点地址
while(head!=null){
next=head.next;//为了防止链表断裂，先储存后一个节点
head.next=pre;//保存完next，让当前结点与链表断开,就可以让head从指向next变成指向pre，即指向前一个节点，完成反转
pre=head; // //pre指针指向当前结点
head=next; // //head指向next(保存着原链表中head的下一个结点地址)
}
return pre;
}
}
解题三-存储数组（代码有待提高）
1.思路
由于题目并没有要求必须原地反转，因此可以借助外部空间实现。这里可以将单链表储存为数组，然后按照数组的索引逆序进行反转。但是，此方式比较浪费空间，而且需要两次遍历，效率不占优势。
2.代码
/*
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;
}
List<Node> nodeList = new List<Node>();
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;
}
}
网友评论