题解 | #反转链表#
反转链表
https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ public ListNode ReverseList (ListNode head) { if (head != null && head.next != null) { ListNode ActualNext = head.next; ListNode lastNode = ReverseList(head.next); head.next = null; ActualNext.next =head; return lastNode; } return head; } }
这道题做过无数八次了,但是再看还是会想半天,抓耳挠腮不堪其扰,现在我把思路记下来当做以后的提示总可以了吧!
反转链表:顾名思义就是把正向的指向变成翻过来如:1->2->3 变成 3->2->1,初看应该很简单直接循环把 node 节点保存在 list 中再反向遍历 list 把 node 一个一个的 next 到前一个后面。
这种办法可行但是太过于暴力,时间复杂度太高了。相同的数据进行循环,那能不能用递归来解决呢?
我们是要把下一个 node 变成前一个 node 的父节点,那我们就先在代码里面写下 head.next 获取到下一个节点吧!我们是要最后把 lastnode 节点给返回成父节点的,所以直接进行递归传入 head.next 返回的 node 就是我们的 lastnode 节点,好了往下走我们进行 head.next.next的赋值ActualNext.next =head;在把 head.next = null 断开和后一个节点的联系。这样 1 节点后面就不会是 2了。
完美!!!
#编程算法学习#