反转链表的四种写法总结

> 1.双指针法：

/*struct ListNode{
   int val;
   struct ListNode *next;       //定义一个结构体ListNode的指针：struct ListNode *next;即每个节点的next指针
    ListNode(int x) :             //结构体的含参构造函数的定义方法：构造体的名称（参数类型 参数名）：变量名（初始化的值），变量名（初始化的值）最后再加一个{},注意next（null）后面没有；
            val(x), next(NULL) {
    }
};*/
class Solution {    //定义一个类名为Solution
public:             //公有函数
    ListNode* ReverseList(ListNode* head) {     //由于要返回的是节点的指针，所以返回值类型是ListNode*，这个函数的名为ReverseList,参数是ListNode类型的头指针head，所以定义为ListNode* head
        ListNode *pre=nullptr;         //定义一个节点指针为*pre 初始化为空指针 *pre=nullptr，pre指针用于存储反转后的节点
        ListNode *cur=head;           //定义一个*cur指针，初始化为头结点，用于存当前的节点
        while(cur!=nullptr){           //只要当前节点还没到空节点，就表明还有节点没有反转
             ListNode *cur_next=cur->next;      //在反转指针之前要先记录下当前指针的后一个节点是谁，否则反转之后就cur->next=pre了，最后更新的时候就不知道原先没反转之前的当前节点的后一个节点是谁,所以创建一个节点指针*cur_next，用于存当前节点的后一个节点
             cur->next=pre;        //存好后就可以将cur的next指针进行反转，指向pre
             pre=cur;              //之后再更新下一轮中反转后的节点就是本轮的当前节点 pre=cur;
             cur=cur_next;         //下一轮的当前节点就是本轮的当前节点的后一个节点
        }
        return pre;       //最后返回pre，就是反转后的链表的头结点
    }
};

> 递归写法

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode reverse (ListNode pre,ListNode cur){
        if(cur==null){
             return pre;
        }
        ListNode cur_next;
        cur_next=cur.next;
        cur.next=pre;
       return  reverse(cur,cur_next);
    }
    public ListNode ReverseList(ListNode head) {
        return reverse(null,head);
    }
}

> 双链表写法

public class Solution{                                 //定义一个类名为Solution，用来通过创建一个新的链表来实现反转链表
    public ListNode ReverseList(ListNode head){        //定义一个函数读入原链表的头结点
        ListNode newhead=null;                         //新创建一个链表，新链表的头结点newhead指向null
           ListNode temp;                                 //只要原链表的头结点还没有指向null，即还没有完全摘除原链表里的节点到新的链表中，就继续
        while(head!=null){                             //由于实际上将原链表上的节点摘下来放在新的链表的头节点处的过程，其实是相当于将新链表连接到当前原链表的head之后
            temp=head.next;                            //所以在将新链表插入head的后面之前，要先将head后面的节点先存起来，存在temp中
            head.next=newhead;                         //存好head后面的节点后，就可以将新链表插入head之后了，就是将head.next=newhead
            newhead=head;                              //之后再更新newhead的值，因为将新链表插入原链表head的后面之后，形成的新链表的newhead更新为head
            head=temp;                                 //而在下一轮的插入的位置是当前head节点的后一个节点temp，即下一轮中temp是作为head
        }
        return newhead;                                //最后得到的新链表的newhead即反转后的链表的头结点

    }
}

> 栈（先进后出）

import java.util.Stack;//因为要用到Java中的Stack类的函数，所以导入（import）Java中的名为util的包中的Stack类
public class Solution{             //定义一个Solution类用于解决用栈（先入后出）的性质来反转链表
    public ListNode ReverseList(ListNode head){     //定义一个ReverseList函数，读入链表的头结点
       Stack<ListNode> stack=new Stack<>();  //调用Stack栈，用new调用Stack<>()无参模板化的构造函数创建一个对象（该对象栈是一个以ListNode为元素的栈）由于这里的Stack是进行过模板化的，所以这里要表明其栈中元素的类型
        while(head!=null){          //只要头结点不为空，即链表中还有元素没入栈，那么就循环
            stack.push(head);       //将链表的头结点调用Stack中的push（）函数进行将元素入栈
            head=head.next;          //接下来由于要把链表中的下一个元素入栈，所以头结点更新为下一个节点，再将该节点入栈
        }
        if(stack.empty()){          //将链表中的所有的元素都入栈后，先判断栈是否为空，调用Stack中的empty()函数进行判断
            return null;            //如果栈为空，那么就直接将返回null
        }
        ListNode dummy=stack.pop();     //否则就创建一个ListNode类型的新的节点dummy，将栈顶元素导出，并存在dummy中，由于最后要返回最开始的栈顶元素，所以不能将dummy进入后面的操作中，因为在后序的操作中或改变栈顶的元素
        ListNode node=dummy;            //所以再新创建一个ListNode类型的节点node，将dummy节点赋值给node
        while(!stack.empty()){           //只要栈还是非空，就将现在的栈顶元素导出并存在temp节点中，接下来再将node.next指向temp节点
            ListNode temp=stack.pop();    //之后再再将新的栈顶元素导出存在temp节点中，并且更新node节点，node更新为node的后一个节点
            node.next=temp;
            node=node.next;
        }
        node.next=null;           //由于为了防止形成环，一定要将最后的node(即反转前的链表的头结点)指向null
        return dummy;             //返回最早的栈顶元素，就是反转后的链表的头结点
    }

}