【链表专题】剑指 Offer 24. 反转链表-跟着帅地玩副业，开拓第二曲线PlayOffer

為愛而生普通 2024年12月31日下午5:59

“`java
//时间On^2 内存On
/**
* 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 null;
ListNode p = head;
int cnt = 0;
ListNode reverse = new ListNode();
ListNode cur = reverse;
while (p.next != null) {
p = p.next;
cnt++;
ListNode node = new ListNode();
cur.next = node;
cur = cur.next;
}
cur = reverse;
int tmp = cnt;
for (int i = 1; i <= cnt + 1; i++) { p = head; for (int j = 1; j <= tmp; j++) p = p.next; tmp--; cur.val = p.val; cur = cur.next; } return reverse; } }

0 赞同 0 条回复

桃桃摇摇奶昔° 普通 2024年12月4日上午10:15

class Solution {
    public ListNode trainningPlan(ListNode head) {
        if (head == null ||head.next==null) return head;
        //方法一 递归
        //递归函数 ： 用于反转链表
        ListNode temp =trainningPlan(head.next);
        head.next.next = head;
        head.next= null;
        return temp;
    }
}

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午2:17

/**
三指针法：
当前指针cur从前往后走，每次将指针往回指，需要借助pre记录cur的前一个位置，tmp记录cur的下一个位置
只遍历一次链表，时间复杂度O(N)
三个指针，空间复杂度O(1)
 */
class Solution {
    public ListNode trainningPlan(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;

    }
}

0 赞同 0 条回复

Carry on 普通 2024年11月29日上午9:20

class Solution {
public ListNode trainningPlan(ListNode head) {
// 原地反转
if(head null || head.next null){
return head;
}

    ListNode cur = head, pre = null;

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

    return pre;

    // 额外空间复杂度=1

}

}

0 赞同 0 条回复

mpweixin用户普通 2024年11月28日下午11:13

递归

# 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 not head:
            return None
        def recur(cur, pre):
            if not cur:
                return pre
            res = recur(cur.next, cur)
            cur.next = pre
            return res
        return recur(head, None)

原地反转

# 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]:
        cur, pre = head, None
        while cur:
            _next = cur.next
            cur.next = pre
            pre = cur
            cur = _next
        return pre

0 赞同 0 条回复

Lil Lee_ 普通 2024年11月27日下午3:31

//双指针
/**
 * 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;
        //cur为当前节点，pre为前置节点
        ListNode cur = head, pre = null;
        while(cur != null){
            //暂存后一节点
            ListNode tmp = cur.next;
            //后一节点等于前一节点
            cur.next = pre;
            //前一等于当前
            pre = cur;
            //当前等
            cur = tmp;
        }
        return pre;
    }
}

0 赞同 0 条回复

前方有星云普通 2024年11月27日上午12:38

class Solution {
public ListNode trainningPlan(ListNode head) {
ListNode pre =null;
ListNode cur = head;
while(cur!= null){
ListNode t = cur.next;
cur.next = pre;
pre=cur;
cur=t;
}
return pre;
}
}打卡

0 赞同 0 条回复

陆狗陆狗普通 2024年11月26日下午10:50

题解【递归】

class Solution {
    public ListNode trainningPlan(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        ListNode nextPlan= trainningPlan(head.next);
        // 【错误点1】
        // head节点指向了nextPlan的尾节点
        // 要让nextPlan的尾节点.next=head节点
        head.next.next=head;
        // 【错误点2】
        // 不然就成环了
        head.next=null;
        return nextPlan;
    }
}

错误点1：trainningPlan(head.next)返回的头结点一定是倒序的nextPlan->4->3->2->null ，并且一定要注意head节点1的指向是没有变过的，一直都是1->2，导致节点2有两个父节点。因此我们的目标就变成了让节点2指向节点1。因而是head.next.next=head
[图片]
错误点2：如果不写head.next=null，会导致成环。2->1，并且1->2，这个在链表中也是不允许存在的。

0 赞同 0 条回复

树懒在橘子洲数星星普通 2024年11月26日下午9:07

“`python
//遍历链表，并在访问各节点时修改next引用指向
class Solution(object):
def trainningPlan(self, head):
cur=head
pre=None
while cur:
tmp=cur.next
cur.next=pre
pre=cur
cur=tmp
return pre
时间复杂度：O(N) N为链表的长度
空间复杂度：O(1) pre cur 额外占用常数的空间

0 赞同 0 条回复

hjx 普通 2024年11月26日下午3:30

代码：class Solution {
public ListNode trainningPlan(ListNode head) {
ListNode pre=null,cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}

0 赞同 0 条回复

hjx 普通 2024年11月26日下午3:30

代码：class Solution {
public ListNode trainningPlan(ListNode head) {
ListNode pre=null,cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}

0 赞同 0 条回复

Rad 普通 2024年11月26日下午2:05

”’java
/**
* 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 || head.next null) {
// 链表为空或者链表只有一个节点时直接返回
return head;
}
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
// 暂存
ListNode temp = cur.next;
// 通过cur与pre进行链表反转
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
”’
时间复杂度On
空间复杂度O1

0 赞同 0 条回复

yelinliner 普通 2024年11月25日下午6:52

###

class Solution {
    public ListNode trainningPlan(ListNode head) {
        // 递归迭代
        // 临界值判断
        if (head == null || head.next == null) {
            // 链表为空或者链表只有一个节点时直接返回
            // or链表已经走到倒数2个了就直接返回
            return head;
        }
        ListNode temp = trainningPlan(head.next);
        // 调整最后两个节点的顺序
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

时间复杂度0(n)、空间复杂度O(n)

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与pre进行链表反转
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度0(n)、空间复杂度O(1)

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月24日下午10:12

/**
* 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 pre = null, cnt = head, temp = null;
while (cnt != null) {
temp = cnt.next;
cnt.next = pre;
pre = cnt;
cnt = temp;
}
return pre;
}
}//运用指针

0 赞同 0 条回复

LovLe 普通 2024年11月24日下午3:31

递归

# 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 not head: return head    #头节点为空
        if not head.next: return head   #单独只有一个节点，直接返回该节点，不用翻转

        temp=self.trainningPlan(head.next)  #后续要翻转的节点，作为返回值
        head.next.next=head #考虑一个节点的翻转（此时已经至少有两个节点存在）
        head.next=None  # 原来的节点指向None!!!不能忘记

        return temp #返回后续节点

时间复杂度为：O(n)

空间复杂度为：O(n) 递归调用消耗栈空间

迭代

# 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 not head or not head.next: return head
        pre=None    #pre初始化为None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur #一定要先更新pre
            cur=temp
        return pre      #返回pre

时间复杂度为：O(n)

空间复杂度为：O(1)

0 赞同 0 条回复

无言永久会员 2024年11月24日下午1: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) {
        //原地反转
        ListNode* newHead = nullptr;
        ListNode* cur = head; // 未被反转的节点
        while(cur) { 
            ListNode* node = cur->next; // 记录当前未被反转的节点的下一节点 方便更新节点
            cur->next = newHead; // 反转节点
            newHead = cur;
            cur = node; // 更新当前未被反转的节点
        }
        return newHead;

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

0 赞同 0 条回复

捕风永久会员 2024年11月24日上午10:50

/**
 * 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 || head.next == null){
            return head;
        }

        // 递归反转子链表
        ListNode temp = trainningPlan(head.next);
        // 将指针指向反转后的链表
        head.next.next = head;
        // 将头节点指向尾部null
        head.next = null;

        return temp;

    }
}

0 赞同 0 条回复

岱永久会员 2024年11月23日下午10:41

先理解遍历的逻辑再想递归会比较好理解

 //双指针
// class Solution {
//     public ListNode trainningPlan(ListNode head) {
//         ListNode cur = head, pre = null;
//         while(cur != null){
//             ListNode t = cur.next;//暂存下一个节点
//             cur.next = pre;
//             pre = cur;
//             cur = t;
//         }
//         return pre;
//     }

// }
//递归
class Solution {
    public ListNode trainningPlan(ListNode head) {
        return recur(head, null);
    }

    private ListNode recur(ListNode cur, ListNode pre){
        if(cur == null) return pre;
        ListNode res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;
        return res;
    }

}

0 赞同 0 条回复

biangbb 普通 2024年11月23日下午9:50

//递归1
class Solution {
public ListNode trainningPlan(ListNode head) {
return recur(head,null);//cur pre
}
ListNode recur(ListNode cur,ListNode pre){
if(curnull)
return pre;//pre是头
ListNode res=recur(cur.next,cur);
cur.next=pre;
return res;
}
}

0 赞同 0 条回复

🍊 普通 2024年11月23日下午6:17

头插法
···java
/**
* 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 || head.next null) return head;
ListNode res = new ListNode();
ListNode p = head;
while(p != null){
ListNode next = p.next;
p.next = res.next;
res.next = p;
p = next;
}
return res.next;
}
}

0 赞同 0 条回复

越努力越幸运普通 2024年11月23日上午12:17

“`c++
class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
if(nullptr == head || nullptr == head->next){
return head;
}
ListNode* temp = trainningPlan(head->next);
head->next->next = head;
head->next = nullptr;
return temp;
}
};
“`
//使用递归比较简单且不易出错

0 赞同 0 条回复

Pendulumpal 普通 2024年11月22日下午9:59

双指针
O(n), O(1)

“`c++
ListNode* trainningPlan(ListNode* head) {
ListNode* cur=head;
ListNode* pre=nullptr;
while(cur!=nullptr){
ListNode* temp=cur->next;
cur->next=pre;
pre=cur;
cur=temp;
}
return pre;
}
“`

0 赞同 0 条回复

Kisara 普通 2024年11月22日下午9:21

““java
递归方法：
class Solution {
ListNode head2 =new ListNode();
ListNode p=head2;
public ListNode trainningPlan(ListNode head) {
reverse(head);
return head2.next;
}

public void reverse(ListNode head){
    if(head==null) {
        return;
    }
    reverse(head.next);
    p.next=new ListNode(head.val);
    p=p.next;
}

//原地遍历法
class Solution {
public ListNode trainningPlan(ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}
O(N) O(1)

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月22日下午8:32

思路：原地遍历，双指针标记法。第二种是递归，结束条件为为空指针或者只有一个节点的链表，递归从后往前将链表关联起来反转
方法1
/**
 * 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 || head.next==null)
            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)
方法2
/**
 * 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 || head.next==null)
            return head;
        ListNode res=trainningPlan(head.next);
        head.next.next=head;
        head.next=null;
        return res;
    }
}
时间复杂度：O(n)
空间复杂度:O(n)

0 赞同 0 条回复

黑键〰普通 2024年11月22日下午4:54

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var trainningPlan = function(head) {
    // if(head == null || head.next == null) return head
    // let p0 = head
    // let pre = null
    // while(p0 !== null) {
    //     let nxt = p0.next
    //     p0.next = pre
    //     pre = p0
    //     p0 = nxt
    // }
    // return pre
    function recur(cur, pre) {
        if(cur === null) return pre
        let res = recur(cur.next, cur)
        cur.next = pre
        return res
    }
    return recur(head, null)
};

思路：两种方式都使用了。原地和递归。递归的时候是想着，一层层往里递归后，从最里层向外回溯，两两操作节点

0 赞同 0 条回复

zing 普通 2024年11月22日上午11:55

递归！！！

class Solution:
    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: 
            return head

        node = self.trainningPlan(head.next)
        head.next.next = head
        head.next = None

        return node

0 赞同 0 条回复

Xiang. 永久会员 2024年11月22日上午9:26

//法一迭代：
class Solution {
public ListNode trainningPlan(ListNode head) {
if (head null||head.nextnull )
return head;
ListNode pre=null;
ListNode cur=head;
ListNode tmp=null;
while(cur!=null){
tmp=cur.next;
cur.next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
}
时间复杂度 O(n)
空间复杂度 O(1)
*/

//法二递归：

class Solution {
public ListNode trainningPlan(ListNode head) {
return reverse(head,null);
}
ListNode reverse(ListNode cur,ListNode pre){
if(curnull) return pre;
ListNode tmp=cur.next;
cur.next=pre;
return reverse(tmp,cur);
}
}
时间复杂度 O(n)
空间复杂度 O(n)

0 赞同 0 条回复

Firefly 普通 2024年11月22日上午9:05

/**
* 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) {
auto pHead=new ListNode();
auto p=head,q=head;
while(p!=nullptr)
{
q=p->next;
p->next=pHead->next;
pHead->next=p;
p=q;
}
p=pHead->next;
delete pHead;
return p;
}
};
使用头指针

0 赞同 0 条回复

youngsir 普通 2024年11月22日上午9:04

“`C++
class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
if(head==nullptr || head->next == nullptr){
return head;
}
ListNode* cur = trainningPlan(head->next);
head->next->next = head;
head->next = nullptr;
return cur;
}
};
“`
时间复杂度O（n）,空间复杂度O（n）

0 赞同 0 条回复

jaron 普通 2024年11月22日上午8:35

递归

时间复杂度：O(N)

额外空间复杂度 O(n)

class Solution {
    public ListNode trainningPlan(ListNode head) {
        // base case
        if(head == null || head.next == null){
            return head;
        }
        // 找到新的头结点一层层返回
        ListNode newHead = trainningPlan(head.next);
        // 每一次递归调用中的head不一样
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

原地反转

时间复杂度：O(N)

额外空间复杂度 O(1)

class Solution {
    public ListNode trainningPlan(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null){
            // 保存cur的next
            ListNode temp = cur.next;
            cur.next = pre;
            // 先把cur给pre
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

0 赞同 0 条回复

Tom Yuan 普通 2024年11月22日上午3:56

方法1：单独把值倒序拉出来然后重新建立link。

class Solution:
    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is []: return []

        stack = []
        temp = head
        while temp is not None:
            stack.append(temp.val)
            temp = temp.next

        new_head = ListNode(0)
        temp = new_head
        for i in range(len(stack)):
            temp.next = ListNode(stack.pop())
            temp = temp.next

        return new_head.next

time O(n) space O(n)

方法2：递归本质也有一个n长度的stack，重新链接回head的部分要注意。

class Solution:
    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: return head

        # we cannot use head other wise this will not actually run.
        temp = self.trainningPlan(head.next)

        # update the head's link, tricky part
        # 5 -> 4 -> 3 -> 2
        #                ^
        #                |
        #                1
        head.next.next = head # head is 1, 1's next is 2, then change its next back to 1
        head.next = None # reconfirm the original head is the tail with None as next

        # time O(n) space O(n) because of the stack.

        return temp

time O(n) space O(n)

方法3：in place重建链接，需要用到一些缓存的点来保证前后关系，用到了双指针的思想。

class Solution:
    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None: return head

        cur = head
        pre = None
        while cur:
            temp = cur.next # temp store the cur.next
            cur.next = pre # reverse the link
            pre = cur # update the previous to be the current visited
            cur = temp # update the current to pre-stored next

        return pre

time O(n) space O(1) 仅额外开了两个node的空间。

0 赞同 0 条回复

mpweixin用户普通 2024年11月22日上午12:58

class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
if(head NULL || head->next NULL){
return head;
}
ListNode* p = head;
ListNode* q = NULL;
while(p){
ListNode* temp = p->next;
p->next = q;
q = p;
p = temp;
}
return q;
}
};
思路：控制两个指针一前一后，每走一步改变一次next的赋值，使其指向前方节点，同时另一个指针向后保存断开处下一个指针。
时间复杂度O(N)，空间复杂度O(1)

0 赞同 0 条回复

咕普通 2024年11月22日上午12:05

    def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur, res = head, None
        while cur:
            tmp = cur.next
            cur.next = res
            res = cur 
            cur = tmp
        return res

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

0 赞同 0 条回复

生活在经验里普通 2024年11月21日下午11:26

func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    if head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    node := head.Next // 注意：创建的是 指向 head.Next 的指针！！！
    node.Next = head  // 与原节点是同一个地址, 修改后, 原节点也会改变
    head.Next = nil
    return newHead
}

0 赞同 0 条回复

晓宇普通 2024年11月21日下午10:57

ListNode* reverseList(ListNode* head) {
if(head nullptr || head->next nullptr){
return head;
}
ListNode *res = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return res;
}
时间复杂度o(n) 空间复杂度o(n)

0 赞同 0 条回复

momo 普通 2024年11月21日下午10:37

class Solution:
def trainningPlan(self, head: Optional[ListNode]) -> Optional[ListNode]:
temp = None
cur = head
if head None:
return
while(cur):
nex = cur.next
cur.next = temp
temp = cur
cur = nex
return temp
时间复杂度O(n), 空间复杂度O(n)

0 赞同 0 条回复

Renasc 普通 2024年11月21日下午10:31

时间复杂度O(n), 空间复杂度O(n)

class Solution {
    public ListNode trainningPlan(ListNode head) {
        // 如果只有节点为空或者只有一个节点，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 创建虚拟头结点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy.next;

        // 递归
        ListNode temp = trainningPlan(curr.next);
        curr.next.next = curr;
        curr.next = null;

        return temp;
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月21日下午10:21

还是想不通递归为什么这样写，只能用顺序翻转的方法了

    public ListNode trainningPlan(ListNode head) {
        if(head == null) return null;
        ListNode prev = null;
        ListNode cur = head;
        ListNode aft = null;
        while(cur != null){
            aft = cur.next;
            cur.next = prev;
            prev = cur;
            cur = aft;
        }
        return prev;
    }

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

0 赞同 0 条回复

parsons 普通 2024年11月21日下午9:39

1.建立两个节点，需要一个暂存节点
2.后一个节点指向前一个节点
3.返回pre节点
class Solution {
public:
ListNode* trainningPlan(ListNode* head) {
ListNode *pre = nullptr;
ListNode *cur = head;
while(cur){
ListNode *next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

🌟 普通 2024年11月21日下午8:50

时间On
class Solution {
public:

ListNode* trainningPlan(ListNode* head) {
    // 原地反转
    if (!head)  return nullptr;
    ListNode*pre=nullptr;
    ListNode* cur=head;
    ListNode* tail=cur->next;
    while(tail){
        cur->next=pre;
        pre=cur;
        cur=tail;
        tail=tail->next;

    }
    cur->next=pre;
    return cur;
}

};

0 赞同 0 条回复

Jerry 普通 2024年11月21日下午8:41

时间o(n)空间o(1)

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年11月21日下午8:38

//头插法，时间O(N),空间O(1)
/**
* 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 p1 = new ListNode(-1);
ListNode cur = head;
ListNode nextListNode = head;

    //头插法倒序
    while (cur != null) {
        nextListNode = cur.next;
        cur.next = p1.next;
        p1.next = cur;
        cur = nextListNode;
    }


    return p1.next;
}

}

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日下午8:37

a.思路分析
1.设置虚拟头节点dummyHead为null（因为链表的最后一个节点一定为null)。
2.设置一个当前节点cur，以及下一个节点next。
3.将cur指向dummyHead,然后将dummyHead位置更新为cur的位置，cur的位置更新为next的位置。
4.最后一次，因为cur在循环条件nullptr的位置上，而dummyHead指向的是链表最后一个有效节点，因此返回该节点。
b.代码分析：

class Solution {
public:
    ListNode* trainningPlan(ListNode* head) {
        ListNode* dummyList = nullptr;
        ListNode* cur = head;
        while(cur)
        {
            ListNode* Next = cur->next;
            cur->next = dummyList;
            dummyList = cur;
            cur = Next;
        }
        return dummyList;
    }
};

c.时间复杂度为o(n)，n为链表长度；空间复杂度为o(1),使用了常数级别的额外内存。

0 赞同 0 条回复

lQl 永久会员 2024年11月21日下午8:37

递归:

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

    }
}

0 赞同 0 条回复

苯庸普通 2024年11月21日下午8:37

class Solution {
public ListNode trainningPlan(ListNode head) {
return reverse2(head);
}

ListNode reverse1(ListNode head){
    ListNode pre = null;
    ListNode cur = head;
    while(cur != null){
        ListNode tmp = cur.next;

        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

ListNode reverse2(ListNode head){
    if(head == null || head.next == null)   return head;
    ListNode tmp = reverse2(head.next);
    head.next.next = head;
    head.next = null;
    return tmp;
}

}
思路：1、原地逆转；2、递归
时间：o（n）o（n）
空间：o（1）o（n）

0 赞同 0 条回复

WYX 普通 2024年11月21日下午8:15

思路：原地反转使用头插法

class Solution {
    public ListNode trainningPlan(ListNode head) {
        ListNode ans = new ListNode(-1, null);

        while(head != null){
            ListNode nextNode = head.next;

            head.next = ans.next;
            ans.next = head;
            head = nextNode;
        }

        return ans.next;

    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月21日下午8:06

双指针原地反转链表方法

class Solution {
    public ListNode trainningPlan(ListNode head) {
        // 反转链表：递归 + 双指针
        return reverse(head, null);
    }

    /**
     * 反转 head,end 的链表
     * @param head
     * @param end
     */
    private ListNode reverse(ListNode head, ListNode end) {
        ListNode pre = end, cur = head, tmp = null;
        while (cur != end) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

思路：reverse 方法是以 head 为头节点，end 为尾节点的链表，使用了三个指针 pre、cur 和 tmp；pre 指针指向的是反转的部分链表的头节点，初始值为 end（本题为 null）；cur 指向的是当前正在处理的节点，初始值为 head；tmp 用于暂时存储 cur 的下一个节点，防止修改 cur.next 的指向时出现的链表丢失问题。使用 while 循环，进行更新，直至 cur == end，表明链表反转完成。
时间复杂度：O(n)，遍历了一次链表。
空间复杂度：O(1)，使用了常数级的额外空间。

递归反转链表方法

class Solution {
    public ListNode trainningPlan(ListNode head) {
        // 反转链表：递归 + 双指针
        // return reverse(head, null);

        if(head == null || head.next == null) {
            return head;
        }

        ListNode newHead = trainningPlan(head.next);
        // 递归到最后两个节点时停止，此时反转这两个节点即可。
        head.next.next = head;
        head.next = null;

        // 返回链表的新头节点
        return newHead;
    }
}

思路：递归结束条件为当链表为空或只有一个节点时，直接返回当前节点 head；不断的递归，直至 head == null || head.next == null，得到从 head.next 开始反转的链表的头节点 newHead；递归到最后，只剩下两个节点，反转这两个节点即可；最后返回反转后的新链表头节点 newHead。
时间复杂度：O(n)，递归遍历时，每个节点都被访问了一次。
空间复杂度：O(n)，递归调用时，栈的深度就是链表的长度。

0 赞同 0 条回复

【链表专题】剑指 Offer 24. 反转链表

共以下 47 个回答

递归

迭代

# 回答此问题取消回复

【链表专题】剑指 Offer 24. 反转链表

共以下 47 个回答

递归

迭代

# 回答此问题 取消回复

# 回答此问题取消回复