Day5|206.反转链表

反转链表主要是要想清楚 首节点 临时节点 以及最后的头结点 可以画个链表 会清晰一些/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */classSolution{publicListNodereverseList(ListNodehead){ListNodeprenull;ListNodecurhead;ListNodetempnull;while(cur!null){tempcur.next;cur.nextpre;precur;curtemp;}returnpre;}}递归法:递归的核心思想反转链表本质上是将每个节点的 next 指针从指向后一个节点改为指向前一个节点。递归方法采用“从前往后”的方式每次处理一个节点先保存当前节点的下一个节点temp因为下一步要修改 cur.next会丢失原来的下一个节点。将当前节点的 next 指向 prev即前一个节点完成当前节点的反转。然后递归处理下一个节点原来的 temp并将当前节点作为新的 prev 传入。当 cur 变成 null 时说明已经处理完所有节点此时 prev 指向原链表的最后一个节点也就是反转后的新头节点返回它。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */classSolution{publicListNodereverseList(ListNodehead){//递归法returnreverse(null,head);}privateListNodereverse(ListNodepre,ListNodecur){if(curnull){returnpre;}//保存下一个节点ListNodetempcur.next;cur.nextpre;//递归调用 传入新的pre cur ,pre变为cur ,cur变成tempreturnreverse(cur,temp);}}