力扣--LCR 141.训练计划III

题目

给定一个头节点为 head 的单链表用于记录一系列核心肌群训练编号，请将该系列训练编号 倒序 记录于链表并返回。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

代码

/**

• 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; }
  

• }
  */
  class Solution {
  public ListNode trainningPlan(ListNode head) {
  if(headnull||head.nextnull){
  return head;
  }
  ListNode cur = head, pre = null;

   while(cur != null){ListNode temp = cur.next;cur.next = pre;pre = cur;cur = temp;}return pre;
  

  }
  }
  时间复杂度：O(N)
  额外空间复杂度 O(1)

递归
// 递归
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
// 反转子链表
ListNode temp = reverseList(head.next);
head.next.next = head;
head.next = null;

    return temp;
}

时间复杂度：O(N)
额外空间复杂度 O(n)，递归调用需要消耗栈空间