mpweixin用户普通 2024年5月14日上午11:56

两种方法都打卡成功

0 赞同 0 条回复

梧葳普通 2023年8月29日上午12:54

双指针方法，以后向指针为最终的反转表头
“””
struct ListNode* reverseList(struct ListNode* head){
// 判空
if (head NULL) {
return NULL;
}
// 处理，双指针方法，以post为反转后的头
struct ListNode *cur = head, *pre = NULL, *post = NULL;
while (cur != NULL) {
pre = cur->next;
cur->next = post;
post = cur;
cur = pre;
}
// 返回，cur最后赋值为pre，已和post断开，所以不能以此返回
return post;
}
“””

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月26日下午10:12

思路

解题思路

分为递归和非递归两种方式:

倒叙数组有两种方法，一种是递归的，一种是非递归的

具体实现的话有四种实现方式

非递归的方法:一种是使用类双指针（实际是3个指针）来将数组倒叙，从头到尾将箭头反向；另一种是使用头插法将数据重新插入一遍

递归的有两种，一种是用递归实现3指针，类似于非递归的双指针法；另一种是直接使用子递归实现，处理好父递归和子递归之间的关系即可

解题方法

解题方法

递归法

递归法分为父节点head 调用子递归并处理子递归之间的关系两步实现【注意要设定好分界值】这个递归是从最后一个节点往前修改指向

第二个递归法使用递归实现双指针法【pre cur 去实现改变方向】这个递归是从第一个开始逐渐向后修改指向

非递归法

使用双指针法，从前往后反向指针的指向，直至遍历到最后一个节点

使用头插法将每个节点重新插入到新的链表中，并将新链表的头指针返回【这里可以加一个头结点，防止空指针异常】

复杂度

时间复杂度:

使用递归法和非递归法都是$O(n)$

空间复杂度:

空间复杂度：使用递归法的话，时间复杂度是$O(n)$ 使用非递归法空间复杂度是原地的，没有使用栈，$O(1)$

Code

package 链表;

import java.util.LinkedList;

import javax.xml.soap.Node;

//https://leetcode.cn/problems/reverse-linked-list/

public class _206_反转链表 {

    public static void main(String[] args) {
        ListNode list  =new ListNode(0);
        ListNode list1 =new ListNode(1);
        list.next=list1;
        ListNode list2 =new ListNode(2);
        list1.next=list2;
        ListNode list3 =new ListNode(3);
        list2.next=list3;
        ListNode list4 =new ListNode(4);
        list3.next=list4;
        list4.next=null;

        ListNode temp =list;
        while (temp!=null) {
            System.out.println(temp.toString());
            temp=temp.next;
        }
        list = Solution2(list);
        temp =list;
        while (temp!=null) {
            System.out.println(temp.toString());
            temp=temp.next;
        }
        System.out.println(list);
    }
    /**
     * 这里是使用的循环非递归实现的链表翻转——使用的是双指针 直接从前往后改变next指向
     * @param head
     * @return
     */
    public static ListNode Solution1(ListNode head) {
        if (head==null||head.next==null) {// 链表为空或者只有一个节点
            return head;// 
        }
//      ListNode prev= null;
//      ListNode cur =head;
//      ListNode temp= null;
//      while(cur!=null) {
//          temp = cur.next;
//          cur.next= prev;
//          prev=cur;
//          cur=temp;
//      }
        ListNode prev =null;
        ListNode cur = head;
        ListNode temp = head;// 用来暂存临时节点 保证链表不被断开

        while(cur !=null) {
            temp = cur.next;
            cur.next = prev;
            prev = cur;
//          cur = prev.next;// 这个时候prev.next 指向的是前一个节点 不会往后走 所以报错
            cur =temp;
        }

        return prev;
    }


    /**
     * 使用递归 从第一个节点往后进行翻转 直到翻转到原来链表的最后一个节点
     * 类似于双指针法
     * 
     */

    public static ListNode Solution3(ListNode head) {
        return reverse(null,head);//首次调用递归函数，实现head节点翻转，原head节点的next为空
    }

    private static ListNode reverse( ListNode prev,ListNode cur) {
        if (cur == null) {
            return prev;
        }// 最后的结束条件  相当于实现到链表尾部

        ListNode temp = cur.next;// 提前存储下后边的节点
        cur.next = prev;// 实现翻转
        prev = cur;// 链表后移
        cur =temp;
        return reverse(prev, cur);  
    }


    /**
     *     //使用递归从后往前，先翻转最后一个节点，再往前翻转
     * @param head
     * @return
     */
    public static ListNode Solution2(ListNode head) {
        if (head==null || head.next==null) {
            return head;
        }
        /**
         * 这里先翻转第二个节点开始往后的链表，从后边往前边进行翻转  最后翻转原来链表的head 节点 指向空
         */
        ListNode newhead = Solution2(head.next);// 所以这里一开始就调用递归函数
        //      在每一次解递归的时候，函数返回的值都是改变指向的newhead，newhead指向了原来的尾结点

        ListNode nextListNode =head.next;//head在上一次解递归完成后，指向前一个节点，来实现倒置
        nextListNode.next = head;
        head.next=null;
//      head.next.next = head;
//      head.next = null;       
        return newhead;
    }


    /**
     * 使用新建一个节点的方式 结合头插法实现链表翻转
     */

    public static ListNode Solution4(ListNode head) {
        if (head== null|| head.next == null) {
            return head;
        }
        ListNode newHeadListNode =null;// 创建一个新链表
        ListNode temp = head;
        while(head!=null) {
            temp=temp.next;// 在原来链表上进行后移
            head.next =newHeadListNode;
            newHeadListNode = head;
            head=temp;  
        }
        return newHeadListNode;
    }
}

0 赞同 0 条回复

黎明之前普通 2023年8月24日下午12:39

//第一种方法递归不断的执行递归当递归完成后还有head->next 和head->next->next 需要改变因为head->next->next 是断的需要自行修改
//时间复杂度O(n)和空间复杂度O(n)
if(head NULL &&head->next NULL)zh
return head;
ListNode temp = reverselist(head->next)
head->next = NULL;
head->next->next = head;
return head;
//第二种原地全部的数值进行不停的移动一位，直到移动的当前指针为空时表示转移了全部
//时间复杂度O(n)和空间复杂度O(1)
if(head NULL||head->next NULL)
reuturn head;
ListNode pre = NULL,cur = head;
while(cur!= NULL)
{
ListNode *temp = cur->next;
cur->next = pre;
pre=cur;
cur= temp;
}
return pre；

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月22日上午12:04

class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode pre = nullptr;
ListNodecurr = head ;
ListNode* temp;
while(head)
{
temp = curr->next;
curr->next = pre;
pre = curr;
curr = temp;
}
return pre;
}
};
时间复杂度：O(N)
空间复杂度：o（1）

0 赞同 0 条回复

小火普通 2023年8月21日下午9:39

原地反转：
时间复杂度：o(n)
空间复杂度：o(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        ListNode* res = new ListNode();
        while(cur!=NULL) {
            res = cur->next;
            cur->next = pre;
            pre = cur;
            cur = res;
        }
        return pre;
    }
};

递归
时间复杂度：o(n)
空间复杂度：o(n)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(NULL, head);
    }
    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if(cur==NULL) return pre;
        ListNode* res = cur->next;
        cur->next = pre;
        return reverse(cur, res);
    }
};

0 赞同 0 条回复

Serena 普通 2023年8月20日下午6:03

原地：时间O(n)，空间O(1)
递归：时间O(n)，空间O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        // //1.原地反转
        //空链表/只有一个节点
        // if(head==null || head.next==null) return head;
        //两个以上节点链表
        // ListNode cur=head.next;
        // ListNode nxt=cur.next;
        // cur.next=head;
        // head.next=null;
        // while(nxt!=null){
        //     ListNode temp=nxt.next;
        //     nxt.next=cur;
        //     cur=nxt;
        //     nxt=temp;
        // }
        // return cur;
        //2.递归反转
        if(head==null || head.next==null){
            return head;
        }
        ListNode temp=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return temp;

    }
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月17日下午7:01

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // 递归法
    ListNode* reverseList1(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr; // 每层执行到这里都相当于反向到了头，所以头结点的next必为null
        return newHead;
    }
    // 双指针
    ListNode* reverseList(ListNode* head) {
        ListNode* prePtr = NULL;
        while(head){
            ListNode* tmp = head->next;
            head->next = prePtr;
            prePtr = head;
            head = tmp;
        }       
        return prePtr;
    }
};

0 赞同 0 条回复

谁仁普通 2023年8月17日下午4:06

struct node * reverList(struct node * head)
{
struct node * prev = NULL;
struct node * curr = head;

//开始循环替换，将haad的下一个节点，往前挪，当前的节点又会与下一个节点替换,最终结果的链表会返回到prev链上
while(curr !=NULL)
{
    struct node * next = curr->next;
    curr->next = prev;
    prev = curr;
    curr=next;
}
return prev;

}，该代码为原地反转，时间复杂度为o（n），空间复杂度为o（1）
//递归方式
struct node * reverList2(struct node * head)
{
//判断节点是否为空
if(head NULL || head->next NULL)
{
return head;
}
//通过创造子链，然后递归反转我们的链表节点
struct node *rev = reverList2(head->next);
head->next->next = head;
head->next = NULL;
return rev;
}//时间复杂度O（n）空间复杂度O（n）

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月16日下午11:13

递归反转加原地反转
class Solution {
public ListNode reverseList2(ListNode head) {
if(head null || head.next null){
return head;
}
ListNode pre = null;
ListNode cur = head;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}

 public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode temp = reverseList2(head.next);
    head.next.next = head;
    head.next = null;
    return temp;
}

}

0 赞同 0 条回复

mpweixin用户普通 2023年8月16日下午10:27

打卡
递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {//作用是将以head为头结点的指针进行反转，返回反转后的头结点
        //递归结束条件
        if(head == NULL || head->next == NULL) return head;
        //等价关系式
        ListNode* temp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
    }
};

迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL){
            ListNode* next = cur->next;

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

0 赞同 0 条回复

mpweixin用户普通 2023年8月16日下午10:20

/
//利用双指针，将尾节点通过tmp为媒介一次传递给pre;
//时间复杂度为0(n);
//空间复杂度为o(1);
#include
class Solution {
public:
ListNode reverseList(ListNode* head) {
ListNode pre=NULL,cur=head;

    while(cur){
        ListNode *tmp=cur->next;
        cur->next=pre;
        pre=cur;
        cur=tmp;
    }
    return pre;
}

};

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月16日下午5:16

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode reverseList(ListNode* head) {
/if(headNULL||head->nextNULL){
return head;
}
ListNode *t=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return t;/ //递归：时间复杂度O(n)，空间复杂度O(n)
if(headNULL||head->nextNULL){
return head;
}
ListNode pre=NULL,cur=head;
while(cur!=NULL){
ListNode *t=cur->next;
cur->next=pre;
pre=cur;
cur=t;
}
return pre; //原地反转：时间复杂度O(n)，空间复杂度O(1)
}
};

0 赞同 0 条回复

Miracle· 普通 2023年8月16日下午2:47

时间复杂度：o(n)，空间复杂度o(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode reverseList(ListNode* head) {
ListNode *rhead = nullptr;
ListNode *cur = head;
while (cur) {
ListNode *next = cur->next;
cur->next = rhead;
rhead = cur;
cur = next;
}
return rhead;
}
};

0 赞同 0 条回复

Delete隐身普通 2023年8月15日下午11:25

原地反转：
思路：使用三个指针，一个表示反转后的链表的头指针，一个表示待反转剩余的节点组成的链表的头指针，一个表示辅助节点
时间复杂度：O(n)，空间复杂度：O(1)
class Solution {
public ListNode reverseList(ListNode head) {
if(head null || head.next null) {
return head;
}
ListNode cur = null;
ListNode pre = head;
ListNode temp = head;
while(temp != null) {
temp = pre.next;
pre.next = cur;
cur = pre;
pre = temp;
}
return cur;
}
}

递归反转
思路：每次递归传入链表的下一个节点，每次让参数节点的next指向参数节点实现链表反转，每次返回值是头节点，最后一次递归一定是原来的尾节点也就是反转后链表的头节点，递归结束条件是当传递的节点没有下一个接待你时返回该节点（因为需要让参数接点的next指向参数节点，参数节点指向null）。
时间复杂度：O(n)，空间复杂度：O(n)
class Solution {
public ListNode reverseList(ListNode head) {
// head null，只是防止第一次调用时head为null，后面每次递归head都不会为null
if(head null || head.next null) {
return head;
}
ListNode node = reverseList(head.next);
head.next.next = head;
head.next = null;
// node为原来链表的尾结点，也就是反转后链表的头节点
return node;
}
}

0 赞同 0 条回复

Prime 普通 2023年8月15日下午11:00

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev, curr = None, head
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        return prev

0 赞同 0 条回复

Sheng 永久会员 2023年8月15日下午10:34

时间复杂度O(n)空间复杂度O(n)
思路是递归
”’java
class Solution {
public ListNode reverseList(ListNode head) {
if(head null)
return head;

    if(head.next == null) {
        ListNode node = new ListNode(head.val);
        return node;
    }

    ListNode tmp = reverseList(head.next);

    ListNode tail = tmp;
    while(tail.next!= null) {
        tail = tail.next;
    }
    tail.next = new ListNode(head.val);

    return tmp;

}

}

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月15日下午9:23

非递归
ListNode* reverseList(ListNode* head) {
if(head nullptr) return nullptr;
ListNode* dummy = new ListNode(0);
dummy->next = nullptr;

    ListNode* p = head;
    ListNode* q = head->next;

    while(p){
        p->next = dummy->next;
        dummy->next = p;
        p = q;
        if(q) q = q->next;
    }

    return dummy->next;
}

递归
ListNode* reverseList(ListNode* head) {
if(head nullptr) return nullptr;
if(head->next nullptr){
return head;
}

    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;

    return newHead;
}

0 赞同 0 条回复

Joel 普通 2023年8月15日下午3:26

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head

        # on-site reversion
        # cur, pre = head, None
        # while cur != None:
        #     temp = ListNode()
        #     temp = cur.next
        #     cur.next = pre
        #     pre = cur
        #     cur = temp

        # return pre

        # recursion
        temp = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return temp

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月15日下午2:29

头插法
时间复杂度O（n）
空间复杂度O（1）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null)
            return null;
        ListNode temp = new ListNode(0);
        ListNode pre = head;

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

0 赞同 0 条回复

天亮之前普通 2023年8月15日上午11:47

/**
*打卡
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head null || head.next null) return head;

    ListNode pre = head;
    ListNode a = null;

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

        a = pre;
        pre = temp;
    }
    return a;
}

}

0 赞同 0 条回复

行动派小彩笔普通 2023年8月14日下午11:16

// 递归思想：时间链表长度O(n),递归空间O(n)
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;

    }
};
 // 原地置换，时间O(n),空间O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;

        ListNode *pre = NULL,*cur = head;
        while(cur)
        {
            ListNode *tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

0 赞同 0 条回复

. 永久会员 2023年8月14日下午10:57

// 递归,张张
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) { //这个地方的终止条件就是要么head上来就null，要么head.next指针指向null也就是我们遍历到了head为最后一个节点的时候,然后就开始了回溯；
            return head;//返回4
        }
        ListNode node = reverseList(head.next);//这个地方head.next=5,head =4;
        head.next.next = head; //将四的下个指针的下个指针指向了自身4；也就是将5原本指向null的指针指向了自己；这个时候4和5之间就形成了双向指针，互相指向；
        head.next = null;//因为要反转链表，所以要将4指向5的指针就断开即为null；
        return node;//然后返回node也就是返回5->4 之后往复执行就可以了；
    }
}

0 赞同 0 条回复

sincere 普通 2023年8月14日下午9:21

思路：1、迭代遍历，从左到右 next、cur、pre 三个指针；2、递归遍历，将整个链表看作 <当前 cur> 和 <后面整个链表> 两个节点，递归调用反转函数，本层中只操作这两个节点的反转
复杂度：1、时间复杂度O(n)，空间复杂度O(1)；2、时间复杂度O(n)，空间复杂度O(n)

// 迭代
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;

        while (cur != null) {
            next = cur.next; // 临时记录当前的 next
            cur.next = pre;// 改变当前的指向
            // cur、pre 往后遍历
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

// 递归
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

0 赞同 0 条回复

QQiing 普通 2023年8月14日下午8:59

class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head NULL || head->next NULL){
return head;
}
ListNode* cur;
ListNode* pre;
ListNode* tmp;
cur = head;
pre = NULL;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};
时间复杂度O(n)，空间复杂度O(1)

0 赞同 0 条回复

逸兴遄飞普通 2023年8月14日下午4:44

分别使用两个方法进行解题。
+ 方法一：双指针迭代

class Solution{
    public ListNode reverseList(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        // 使用双指针进行迭代
        ListNode cur = head, pre = null;
        while(cur != null){
            // temp用于存储前序节点的值，在反向赋值时使用
            ListNode temp = cur.next;
            // 对节点进行反向赋值
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

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

方法二：函数递归

class Solution {
    public ListNode reverseList(ListNode head) {
        // 对链表进行边界判断，将空表和单项表直接返回
        if(head == null || head.next == null){
            return head;
        }
        // 对链表节点依次进行递归操作
        ListNode result = reverseList(head.next);
        // 将节点方向修改为反向
        head.next.next = head;
        // 最终指向null
        head.next = null;

        return result; 
    }
}

时间复杂度O(N)，
空间复杂度O(N) : 遍历链表的递归深度达到 N ，系统使用 O(N) 大小额外空间。

0 赞同 0 条回复

mpweixin用户普通 2023年8月14日下午1:31

时间复杂度：O(N), 空间复杂度：O(1)
用中间变量记录下一个节点
原地反转

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = head;
        ListNode cur = null;
        ListNode temp =null;
        if(head == null || head.next == null){
            return head;
        }        

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

        return cur;
    }
}

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

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

0 赞同 0 条回复

晓宇普通 2023年8月14日上午11:09

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        if head==None or head.next == None:
            return head
        tmp = self.reverseList(head.next)
        if head.next.next == None:
            head.next.next = head
            head.next = None
        return tmp

空间复杂度 O(1)
时间复杂度O（N）
本题是主要是两个问题：
1.在何处写链表反转代码，答案是在后续位置而核心代码就是

        if head.next.next == None:
            head.next.next = head
            head.next = None

遇到类似问题可以先把这个代码写完
2、如何把结尾的头返回过来，比较妙的写法是这个return head，因为这样结尾的代码则为return 结尾的代码
而tmp的值在所有递归中都在传递这个值

0 赞同 0 条回复

Marc 普通 2023年8月14日上午1:58

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head   
        while cur:
            nxt, cur.next = cur.next, pre 
            pre, cur = cur, nxt                
        return pre

时间On ，空间O1

0 赞同 0 条回复

JustRtn 普通 2023年8月14日上午1:18

时间复杂度O(n),空间复杂度O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode reverseList(ListNode* head) {
if (head nullptr) {
return nullptr;
}
ListNode *last = nullptr;
ListNode *tmp = head->next;
ListNode *cur = head;
while (tmp != nullptr) {
cur->next = last;
last = cur;
cur = tmp;
tmp = cur->next;
}
cur->next = last;
return cur;
}
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月14日上午1:09

時間複雜度: O(n) 空間複雜度: O(n)
思路: 一樣利用遞歸來解, 首先取得最尾端的node, 並在後序遍歷位置反轉當前node, 最後回傳最尾端node即為結果


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }

        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return last;
  
  
    }

  
};

0 赞同 0 条回复

别扒拉我普通 2023年8月13日下午11:53

1、栈

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {

    public ListNode ReverseList (ListNode head) {
        if(head == null){
            return null;
        }
        Stack<ListNode> stack = new Stack<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode myList = stack.pop();
        ListNode newNode = myList;
        while(!stack.isEmpty()){
            newNode.next = stack.pop();
            newNode = newNode.next;
        }
        newNode.next = null;
        return myList;
    }
}

0 赞同 0 条回复

天亮说晚安普通 2023年8月13日下午11:12

思路：利用栈存储节点值，出栈到新链表返回
时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode p1 = head;
        ListNode res = new ListNode();
        ListNode p2 = res;
        while(p1!=null){
            stack.push(p1);
            p1 = p1.next;
        }
        while(stack.size()>0){
            ListNode t = stack.pop();
            p2.val = t.val;
            if(stack.size()>0)
                p2.next = new ListNode();
            p2 = p2.next;
        }
        return res;
    }
}

0 赞同 0 条回复

clown 普通 2023年8月13日下午11:11

注意的是一定要提前记录好cur下一个节点的地址，因为将next赋值之后就断了
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head null) return null;
if(head.next null) return head;
ListNode cur = head;
// ListNode next_node = cur.next;
ListNode pre = new ListNode(-1);
pre.next = null;
while(cur.next!=null){
ListNode temp = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = temp;
}
cur.next = pre.next;
return cur;
}
}

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月13日下午9:13

“`python
用栈写的

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head None: return None
tmp = ListNode(-1)
tmp.next = head

    s = []

    while head:
        s.append(head.val)
        head = head.next

    head = tmp
    while s:
        node = ListNode(s.pop())
        head.next = node
        head = head.next

    return tmp.next

0 赞同 0 条回复

辰北、普通 2023年8月13日下午5:14

//创建俩，一个原表一个空表，然后借用中间值pnext前插发
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *p1=head;
struct ListNode *p2=NULL;

while(p1){
struct ListNode *pnext=p1->next;
// p2->val=p1->val;
// p2->next=p1->next;
// p1=p1->next;
p1->next=p2;
p2=p1;
p1=pnext;
// free(pnext);

}
return p2;

}

0 赞同 0 条回复

小肸永久会员 2023年8月13日下午5:01

class Solution {
    // public ListNode reverseList(ListNode head) {
    //     return dfs(head, null);
    // }
    // private ListNode dfs(ListNode cur, ListNode pre) {
    //     if (cur == null) {
    //         return pre;
    //     }
    //     //这里res存储反转后链表的头节点，一直都是最初的尾节点。
    //     ListNode res = dfs(cur.next, cur);
    //     cur.next = pre;
    //     return res;
    // }
    //和上面只是递归写法不同，递归过程却是一模一样的
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

0 赞同 0 条回复

c 普通 2023年8月13日下午4:42

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
           return null;
        }
        ListNode node=head;
        ListNode next;
        head=head.next;
        node.next=null;
        while(head!=null){
                next=head.next;
                head.next=node;
                node=head;
                head=next;
        }
        return node;

    }
}

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月13日下午4:18

这里用的是原地翻转，用了两个指针，prev和next。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }

        ListNode prev = null, next = head, temp = head;
        while (next != null){
            temp = next.next;
            next.next = prev;
            prev = next;
            next = temp;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode a1 = new ListNode(1);
        ListNode a2 = new ListNode(2);
        ListNode a3 = new ListNode(3);
        ListNode a4 = new ListNode(4);
        ListNode a5 = new ListNode(5);

        a1.next = a2;
        a2.next = a3;
        a3.next = a4;
        a4.next = a5;

        Solution sol = new Solution();
        ListNode listNode = sol.reverseList(a1);

        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月13日下午2:26

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

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = null;
        while (head != null) {
            ListNode temp  = head.next;
            head.next= dummy.next;
            dummy.next = head;
            head = temp;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

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

共以下 40 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题取消回复

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

共以下 40 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题 取消回复

# 回答此问题取消回复