mpweixin用户普通 2024年4月1日上午11:39

python”’
def trainningPlan(self, head):
“””
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
“””
#递归反转
# 如果链表为空或只有一个节点，直接返回该节点
if head is None or head.next is None:
return head
# 递归
temp = self.trainningPlan(head.next)
head.next.next = head
head.next = None
return temp
时间空间复杂度为O(n)
def trainningPlan(self, head):
“””
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
“””
#原地反转–一个while循环实现，
#通过迭代的方式逐步改变每个节点的next指针，直到整个链表被反转
pre = None
current = head
while current is not None:
next_node = current.next
current.next = pre
pre = current
current = next_node
return pre
时间复杂度O(n),空间复杂度O(1)

0 赞同 0 条回复

晚睡晚起起不来永久会员 2024年3月30日上午11:22

原地反转
首先判断特殊情况head是否为空，head下一个节点是否为空
因为要初始化两个，一个是cur，一个是pre
当cur不为空就进行反转，反转之前要保存一下cur下一个节点的信息，之后整体去移动
最后返回pre，也就是反转后的头节点

java
class Solution {
    public ListNode trainningPlan(ListNode head) {
        //原地反转
//判断特殊情况是否为空
        if(head ==null || head.next ==null) return head;
//初始化节点，cur 和pre
        ListNode cur = head, pre = null;
//当cur存在的时候，进行反转
        while(cur != null){
//temp在反转之前是保存当前节点的下一个节点信息的
            ListNode temp = cur.next;
//cur.next指向pre ，单节点是反转的，while循环后，整个指向就相反了
            cur.next = pre;
//整体移动
            pre = cur;
            cur = temp;
        }
//最后返回pre,其中pre是反转后的头节点，是原链表的尾部
        return pre;

    }
}

递归方法
首先判断特殊情况为空
然后对子链表进行反转，这里lecoode没有提供反转方法会报错
然后把头节点的下一个节点指向头节点，头节点本身指向null
就结束了

java
  // 递归
      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;
    }

0 赞同 0 条回复

晚睡晚起起不来永久会员 2024年3月30日上午11:22

原地反转
首先判断特殊情况head是否为空，head下一个节点是否为空
因为要初始化两个，一个是cur，一个是pre
当cur不为空就进行反转，反转之前要保存一下cur下一个节点的信息，之后整体去移动
最后返回pre，也就是反转后的头节点

java
class Solution {
    public ListNode trainningPlan(ListNode head) {
        //原地反转
//判断特殊情况是否为空
        if(head ==null || head.next ==null) return head;
//初始化节点，cur 和pre
        ListNode cur = head, pre = null;
//当cur存在的时候，进行反转
        while(cur != null){
//temp在反转之前是保存当前节点的下一个节点信息的
            ListNode temp = cur.next;
//cur.next指向pre ，单节点是反转的，while循环后，整个指向就相反了
            cur.next = pre;
//整体移动
            pre = cur;
            cur = temp;
        }
//最后返回pre,其中pre是反转后的头节点，是原链表的尾部
        return pre;

    }
}

递归方法
首先判断特殊情况为空
然后对子链表进行反转，这里lecoode没有提供反转方法会报错
然后把头节点的下一个节点指向头节点，头节点本身指向null
就结束了

java
  // 递归
      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;
    }

0 赞同 0 条回复

山月普通 2024年3月14日下午8:44

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* head) {
// 判断递归结束条件
if(head NULL || head->next NULL)
{
return head;
}
// 递归等式
//反转整个链表等价于反转trainingPlan(head.next)+原地反转第1个链表
ListNode* newListNode = trainningPlan(head->next);

    head->next->next = head;
    head->next =NULL;
    return newListNode;


}

};
//今天学了递归算法，递归要义：确定函数功能，确定结束条件，确定递归等式

0 赞同 0 条回复

RunAsOne 普通 2024年3月11日下午4:29

第六次打卡

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def trainningPlan(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        cur, pre = head, None
        while cur:
            tmp = cur.next # 暂存后继节点 cur.next
            cur.next = pre # 修改 next 引用指向
            pre = cur      # pre 暂存 cur
            cur = tmp      # cur 访问下一节点
        return pre

0 赞同 0 条回复

雨落星空普通 2024年3月10日上午9:43

”’python
class Solution(object):
def reverseList(self, head):
“””
:type head: ListNode
:rtype: ListNode
“””
if head is None or head.next is None:
return head

    # 反转子链表
    temp = self.reverseList(head.next)
    head.next.next = head
    head.next = None

    return temp

0 赞同 0 条回复

Yeah~ 普通 2024年3月6日下午2:19

“`c++
//原地反转，空间O(1)，时间O(n)
class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
ListNode* pre = head;
ListNode* cur = nullptr;
while(pre!=nullptr){
ListNode* tmp = pre;
pre = pre->next;
tmp->next = cur;
cur = tmp;
}
return cur;

};

//递归，时间O(n)，空间O(n)

0 赞同 0 条回复

e=mc² 普通 2024年3月6日上午12:22

// 原地
class Solution {
    public ListNode trainningPlan(ListNode head) {
        ListNode pre =null;
        // 不影响原链表
        ListNode cur = head;
        while (cur != null) {
            // 保存未遍历到的部分
            ListNode temp = cur.next;
            // 取下一位，使其next拼接上已经倒转的部分
            cur.next = pre;
            // 保存已经遍历的部分
            pre = cur;
            //继续遍历
            cur = temp;
        }
        return pre;
    }
}
时间复杂度：O(n)
时间复杂度：O(1)

//递归
class Solution {
    public ListNode trainningPlan(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 没有复制新的链表
        ListNode newHead = trainningPlan(head.next);
        // 改变的是next指针的指向
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

湘江小水鬼普通 2024年3月5日下午10:06

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
*/
struct ListNode reverseList(struct ListNode* head) {
struct ListNode* pre = NULL;
struct ListNode* cur = head;
while(cur!=NULL){
struct ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}打卡

0 赞同 0 条回复

YOLO 普通 2024年3月5日下午7:34

 //定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
class Solution {
    public ListNode trainningPlan(ListNode head) {
        if(head==null||head.next==null)
            return head;

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

0 赞同 0 条回复

C C 普通 2024年3月5日下午7:15

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        # 反转子链表
        temp = self.trainningPlan(head.next)
        head.next.next = head
        head.next = None

        return temp

0 赞同 0 条回复

神经蛙普通 2024年3月5日上午10:38

class Solution {
    public ListNode trainningPlan(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode pre = null, cur = head;

        while(cur != null){
            ListNode n = cur.next;
            // 交换指向
            cur.next = pre;
            // 移动
            pre = cur;
            cur = n;
        }

        return pre;
    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月5日上午8:02

时间：O(n)
空间：O(1)

class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;

        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur) {
            ListNode* nextNode = cur->next; // 保留cur的下一个点
            cur->next = pre; // 然后每次只改变两个节点之间的那个指针方向
            pre = cur;
            cur = nextNode; // cur移动到下一个点
        }
        return pre;
    }
};
时间：O(n)
空间：O(n)
class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* newHead = trainningPlan(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

0 赞同 0 条回复

时生普通 2024年3月5日上午12:16

//使用头插法进行反转
struct ListNode* trainningPlan(struct ListNode* head) {
typedef struct ListNode ListNode;
if(head NULL){
return NULL;
}
ListNode *p = head->next;
head->next = NULL;
ListNode *r =NULL;
while(p!=NULL){
r=p->next;
p->next = head;
head = p;
p = r;
}

return head;

}

0 赞同 0 条回复

繁星普通 2024年3月4日下午11:33

方法一：双指针，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public ListNode trainningPlan(ListNode head) {
if(head null || head.next null) return head;
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode curNext = cur.next;
cur.next = pre;
pre = cur;
cur = curNext;
}
return pre;
}
}
方法二：递归，时间复杂度O(n)，空间复杂度O(1)
class Solution {
ListNode res = null;
public ListNode trainningPlan(ListNode head) {
ListNode pre = null;
recursion(head,pre);
return res;
}
public void recursion(ListNode cur,ListNode pre) {
if(cur null) {
res = pre;
return;
}
recursion(cur.next, cur);
cur.next = pre;
}
}

0 赞同 0 条回复

莫～慢～待普通 2024年3月4日下午11:16

public ListNode trainningPlan(ListNode head)
{
if(headnull||head.nextnull)
return head;
ListNode pre=trainningPlan(head.next);
head.next.next=head;
head.next=null;
return pre;
}
利用递归方式，从后往前反转链表
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

30tcq 普通 2024年3月4日下午8:17

//思路：双指针，不停修改cur和pre，但是每次都提前存下cur->next
//思路一：每次都让cur指向pre,同时为了向后走，提前记录next
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* head) {
if(head NULL || head->next NULL) return head;
ListNode *pre = NULL;
ListNode *cur = head;
ListNode *tmp;

    while(cur != NULL){
        tmp = cur->next;
        cur->next = pre;                                                                                           
        pre = cur;
        cur = tmp; 
    }
    return pre;
}

};
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

=.= 普通 2024年3月4日下午7:59

/**
* 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(head null) return head;

    ListNode pre = null;
    ListNode cur = head;

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

    return pre;
}

}

时间复杂度O(n)，空间复杂度O(1)

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午5:33

public ListNode trainningPlan(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null) {
ListNode tmp = cur.next; // 暂存后继节点 cur.next
cur.next = pre; // 修改 next 引用指向
pre = cur; // pre 暂存 cur
cur = tmp; // cur 访问下一节点
}
return pre;
}
思路：cur指向当前把cur的前一个变成cur的后一个
时间 n 空间1

0 赞同 0 条回复

　南木普通 2024年3月4日下午5:15

原地反转，空间复杂度O(1),时间复杂度O(n)

/**
 * 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) {
        ListNode cur = head,pre = null;
        ListNode temp = new ListNode();
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

0 赞同 0 条回复

小耿普通 2024年3月4日下午4:11

“`C++
class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;

    if (!head) return head; //nullptr
    ListNode* tmp = nullptr;

    while(cur) {
        tmp = cur->next;
        cur->next = pre;
        pre = cur;  // 这个不能忘记移动
        if (tmp == nullptr) break;  // 这个判断
        cur = tmp;
    }
    return cur;
}

};

“`

0 赞同 0 条回复

阿野普通 2024年3月4日下午4:11

#打卡
var trainningPlan = function(head) {
if (head null || head.next null) {
return head;
}
const newHead = trainningPlan(head.next);
head.next.next = head;
head.next = null;
return newHead;
};

0 赞同 0 条回复

南梁陈庆之普通 2024年3月4日下午3:50

class Solution {
    public ListNode trainningPlan(ListNode head) {
       ListNode cur = head, pre = null;

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

    }
}

时间复杂度 O（N）
空间复杂度O（1）

定义当前节点cur，前节点pre和临时节点tmp；设法让当前节点指向前节点；
1、临时节点指向cur的下一个节点
2、当前节点的下一个节点修改指向为前节点
3、前节点修改为当前节点
4、当前节点修改为临时节点

0 赞同 0 条回复

kfaebot 普通 2024年3月4日下午3:41

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        ListNode *tmp=nullptr;
        ListNode *slow=nullptr;
        ListNode *fast=head;

        //如果链表为空或者链表只有一个元素，直接返回
        if(head==nullptr||head->next==nullptr){
            return head;
        }
        while(fast!=nullptr){
            tmp=fast->next;
            fast->next=slow;
            slow=fast;
            fast=tmp;
        }
        return slow;
    }
};
\\双指针原地反转
\\时间复杂度O(N)，空间复杂度O(1)

0 赞同 0 条回复

Jankin 普通 2024年3月4日下午1:30

/**
 * 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 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;

        // 迭代
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

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

0 赞同 0 条回复

一个达不刘普通 2024年3月4日上午10:35

思路：
用三个指针，遍历链表，执行断链，重定向，将原链表逆序，输出

class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
ListNode *cur = head, *pre =nullptr;
while(cur != nullptr){
ListNode *temp = cur->next;//暂存后继结点
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};

0 赞同 0 条回复

Eugene 普通 2024年3月4日上午8:37

Definition for singly-linked list.

class ListNode(object):

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution(object):
def trainningPlan(self, head):
“””
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
“””
if head is None:
return None

    node = ListNode(head.val)
    while head.next is not None:
        node = ListNode(head.next.val, node)
        head = head.next
    return node

常规

0 赞同 0 条回复

mpweixin用户普通 2024年3月3日下午10:03

java
class Solution {
public ListNode trainningPlan(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
提交

0 赞同 0 条回复

东普通 2024年3月3日下午9:57

原地反转
class Solution {
public ListNode reverseList(ListNode head) {

    ListNode pre = null;
    ListNode cur = head;

//tmp用来下一节点，cur用来记录当前节点，pre用来记录上一届点
while (cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}

0 赞同 0 条回复

晚风、普通 2024年3月3日下午9:39

class Solution:
def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
#双指针法
cur,pre=head,None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
时间复杂度：o(n)
空间复杂度：o(n)

0 赞同 0 条回复

晚风、普通 2024年3月3日下午9:39