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

招舟子普通 2023年8月24日下午9:39

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(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 条回复

mpweixin用户普通 2023年7月18日下午10:51

时间：O(n)
空间：O(1)
//原地反转
class Solution {
public ListNode reverseList(ListNode head) {
//原地反转
if(head null || head.next null){
return head;
}
if(head.next.next null){
int tmp = head.next.val;
head.next.val = head.val;
head.val = tmp;
return head;
}
ListNode tmp = head;
ListNode low = head;
ListNode high = head.next;
ListNode tmp1 = high.next;

  while(high!= null){
      high.next = low;
      low = high;
      high = tmp1;
      tmp1 = high.next;
  }
  //high.next还未反转
  high.next = low;
  tmp.next = null;
  return high;
}

}

0 赞同 0 条回复

橙子陈普通 2023年7月15日下午7:20

// 递归 时间复杂度O(n) 空间复杂度O(n)
class Solution {
    public ListNode reverseList(ListNode head) {
        if (null == head || null == head.next) {
            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 (null == head || head.next == null) return head;

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

        return pre;
    }
}

0 赞同 0 条回复

ZJS 永久会员 2023年7月15日上午11:33

原地反转
时间复杂度：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 curr = head;

        while(curr.next != null){
            ListNode temp = curr.next;
            curr.next = curr.next.next;
            temp.next = head;
            head = temp;
        }

        return head;
    }
}

方法：递归
时间复杂度：O(n)
空间复杂度：O(n)

class Solution {
    public ListNode reverseList(ListNode head) {
        return recu(head);
    }

    //将以head为头节点的链表反转，并返回头节点
    ListNode recu(ListNode head){
        // base case
        // 如果链表为空或只有一个元素，直接返回即可
        if(head == null || head.next == null){
            return head;
        }

        // 这里已经将head节点后的链表反转过来了，并返回了新的头节点
        ListNode last = recu(head.next);

        // 将当前的头节点变成新链表的尾节点
        head.next.next = head;
        head.next = null;

        return last;

    }
}

0 赞同 0 条回复

TT 永久会员 2023年7月9日下午5:05

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null, temp;
        while(cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}
时间复杂度O(n)
空间复杂度O(1)

0 赞同 0 条回复

cute. 普通 2023年7月5日下午5:40

思路：使用两个指针【前驱指针、当前指针】进行反转

var reverseList = function(head) {
    if (head === null || head.next === null)
        return head;
    let cur = head;
    let pre = null;
    while (cur !== null) {
        let temp = cur.next;
        cur.next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
};

0 赞同 0 条回复

与你同行普通 2023年7月3日下午5:05

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    // 1. var newHead = new(ListNode) 
    // 2. var newHead *ListNode = nil 
    // 1 和 2 的区别： 
    // 2 是*ListNode 的零值 
    // 1 等价于 var newHead = &ListNode{Val:0, Next:nil} 
    // 本题 newHead 初始值是反转之后的尾节点, 所以需要 nil
    var pre *ListNode = nil
    cur := head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

0 赞同 0 条回复

淡色花樱普通 2023年7月3日下午12:56

“`java
class Solution{
Public ListNode reverseList(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 条回复

Gracelyne 普通 2023年7月2日下午2:10

时间：O（n), 空间 O（1）
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *next, *prev = NULL;
        ListNode* cur = new ListNode(-1);
        cur = head;

        while(cur != NULL){
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        head = prev;
        return head;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月1日下午12:55

利用递归到达链表的尾部，然后通过一个全局的Node来从尾部依次链接节点

class Solution {
    private static ListNode ans;
    public void getNode(ListNode head){
        if(head==null){
            return;
        }
        getNode(head.next);
        ans.next=head;
        ans=ans.next;
    }
    public ListNode reverseList(ListNode head) {
        ans=new ListNode(0);
        ListNode temp=ans;
        getNode(head);
        ans.next=null;
        return temp.next;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午10:51

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

时间复杂度O(N), 空间复杂度O（1）

0 赞同 0 条回复

Sexypig. 普通 2023年6月28日下午10:17

代码：

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

时间复杂度：O（n），需要遍历一次链表
空间复杂度：O（n），递归栈的大小为链表长度

0 赞同 0 条回复

baoyou 普通 2023年6月28日下午10:09

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 || head.next == null) {
            return head;
        }
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

时间复杂度：O(n)
额外空间复杂度：O(n)

2.原地反转

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

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

0 赞同 0 条回复

大大普通 2023年6月28日下午8:10

 
法一：迭代
//设置头尾指针
class Solution {
public:
    ListNode* reverseList(ListNode* head) {//头尾节点
     ListNode* cur=head;
     ListNode* pre=NULL;
     while(cur){
      ListNode* temp=cur->next;//注意保留原来的数据
      cur->next=pre;
      pre=cur;
      cur=temp;
     }
      return pre;
    }
};



法二：递归

class Solution {
public:
//递归解决
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL)return head;
        ListNode* newList=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return newList;
    }
};

0 赞同 0 条回复

浅伤永久会员 2023年6月28日下午5:00

时间复杂度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) {

        ListNode pre = null, cur = head;

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

            cur.next = pre;

            pre = cur;
            cur = tmp;

        }
        return pre;

    }
}

0 赞同 0 条回复

泡芙永久会员 2023年6月27日下午8:23

方法一：原地反转（迭代）+ 双指针

Time：O(n)

Space：O(1)

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

        ListNode cur = head;
        ListNode pre = null;

        while(cur != null) {
            // temp 保存后面的节点防止丢失
            ListNode temp = cur.next;
            // 反转操作
            cur.next = pre;
            // 更新 pre 和 cur 指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

方法二：递归

Time：O(n)

Space：O(n)

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 条回复

Yangon 普通 2023年6月27日下午6:55

反转链表

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


    }

}

0 赞同 0 条回复

mpweixin用户普通 2023年6月26日下午10:30

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

   pre = None # 虚拟节点
    cur = head
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre

使用双指针法，原地反转链表

0 赞同 0 条回复

HU 普通 2023年6月25日下午8:12

方法1：递归。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 1. 找寻结束条件
    if(head === null || head.next === null) {
        return head;
    }
    let newNode = reverseList(head.next);
    // 找寻节点2
    let node2 = head.next;
    node2.next = head;
    head.next = null;
    return newNode;
};

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

方法2：原地反转。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 先保存当前节点
    let cur = head;
    // 设置前驱节点
    let pre = null;
    while(cur) {
        // 保存当前节点的下一个节点
        let temp = cur.next;
        // 反转当前节点
        cur.next = pre;
        // 前驱节点和当前节点向后移动一位
        pre = cur;
        cur = temp;
    }
    return pre;
};

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月24日下午9:25

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 pre =null;
        ListNode cur = head;

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

        return pre;


    }
}

2、递归反转

/**
 * 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 tmp = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return tmp;
    }
}

0 赞同 0 条回复

未来已来~ 普通 2023年6月24日下午4:48

/**
 * Java 代码
 * 思路1. 递归
 * 思路2. 原地反转
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 链表为空或只有一个结点时
        if(head == null || head.next == null) {
            return head;
        }

        /*
         * 思路1. 递归
         * 时间复杂度: O(n)
         * 空间复杂度: O(n),递归调用需要消耗栈空间
         */
         /*
        // 反转子链表
        ListNode temp = reverseList(head.next);
        // 此时原链表的第二个结点值就是反转链表的最后一个结点值,将原链表原链表的第二个结点值指向头结点,头结点指向null,即可实现整个链表反转
        head.next.next = head;
        head.next = null;

        return temp;  */

        /*
         * 思路2. 原地反转
         * 时间复杂度: O(n)
         * 空间复杂度: O(1)
         */
        ListNode cur = head, pre = null;

        while (cur != null) {
            ListNode temp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;   // 修改next引用指向
            // 整体前移
            pre = cur;        // pre 暂存 cur
            cur = temp;       // cur 访问下一结点            
        }
        // cur == null 时
        return pre; // 此时 pre 指向链表最后一个结点,cur指向null表示结束
    }
}

0 赞同 0 条回复

BOZ 普通 2023年6月24日上午11:34

【思路】向后遍历的同时往新链表头插入节点
【复杂度】时间O(n)，空间O(1)

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* new_head = NULL, *next = head, *tmp;
        while(next != NULL) {
            tmp = next->next;
            next->next = new_head;
            new_head = next;
            next = tmp;
        }
        return new_head;
    }
};

0 赞同 0 条回复

Tang 普通 2023年6月24日上午9:45

“`java /**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
“`
时间复杂度：O(n) 空间复杂度：O(1)

0 赞同 0 条回复

GGBond 普通 2023年6月23日下午9:44

class Solution {
    public ListNode reverseList(ListNode head) {
        //头插法,增加虚拟头结点
        ListNode newHead = new ListNode();
        //插入结点
        ListNode p = head;
        while(p != null){
            //保存插入结点的下一个结点
            ListNode temp = p.next;
            p.next = newHead.next;
            newHead.next = p;
            p = temp;
        }
        return newHead.next;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        //双指针,前后指针改变 链接方向
        ListNode before = head;
        ListNode after = null;
        while(before != null){
            //保存下一个结点
            ListNode temp = before.next;
            before.next = after;

            after = before;
            before = temp;
        }
        return after;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归解法，和双指针是一样的

        return reverse(head,null);
    }

    public ListNode reverse(ListNode pre,ListNode back){
        if(pre == null){
            //返回新头结点
            return back;
        }
        //先反转尾部
        ListNode head = reverse(pre.next,pre);
        pre.next = back;
        return head;
    }
}

0 赞同 0 条回复

地平线真勇敢普通 2023年6月23日下午9:09

java反转链表
public ListNode reverseList(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;
}
时间复杂度o(n)
空间复杂度o(1）

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月23日下午4:53

打卡

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

    let temp = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return temp;

};

0 赞同 0 条回复

WhyBeBubble 普通 2023年6月22日下午11:02

ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
auto newHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}

0 赞同 0 条回复

Yodl. 普通 2023年6月22日下午10:11

递归 时间复杂度O(n) 空间复杂度O(n)
class Solution {
public:
    void fun(ListNode* p,ListNode* q)
    {
        if(p==NULL)
        {
            return;
        }
        fun(p->next,q->next);
        p->next=q;
        q->next=NULL;
    }
    ListNode* reverseList(ListNode* head) {
        ListNode *p=head,*q;
        if(p==NULL)
        {
            return p;
        }
        if(p->next==NULL)
        {
            return p;
        }
        while(p->next!=NULL)
        {
            p=p->next;
        }
        ListNode *ans=p;
        p=head->next;
        q=head;
        fun(p,q);
        return ans;
    }
};

头插法 时间复杂度O(n) 空间复杂度O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 头插法 中间变量保存下一个结点坐标
        ListNode* r = head;
        ListNode* newn = new ListNode(-1);
        newn->next = NULL;
        ListNode* ret = newn;
        ListNode* q;
        while (r!=NULL)
        {
            q = r->next;
            r->next = newn->next;
            newn->next = r;
            r = q;
        }
        return ret->next;
    }
};

原地反转 时间复杂度O(n) 空间复杂度O(1)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p,*q,*s;
        p=head;//指向当前节点
        q=NULL;//指向前一个节点
        s=NULL;//指向后一个节点
        while(p!=NULL)
        {
            s=p->next;
            p->next=q;
            q=p;
            p=s;
        }
        return q;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午9:10

前中后 pre cur back 三个指针改变next意味着对指向的下个节点的丢失，想要使用要先保存
public ListNode ReverseList(ListNode head) {

    if(head == null){
        return null;
    }

    ListNode cur = head;
    ListNode pre = null;
    ListNode back = null;

    while(cur != null){

        back = cur.next;
        cur.next = pre;

        pre = cur;
        cur = back;

    }

    return pre;
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月22日下午4:11

原地反转 时间复杂度O(n) 空间复杂度O(1)
# 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 not head or not head.next:
            return head
        cur = head
        pre = None
        while cur:
            tmp = cur.next
            cur.next = pre
            pre = cur
            cur = tmp    
        return pre

0 赞同 0 条回复

3_🔥 永久会员 2023年6月22日下午4:05

class Solution {
    public ListNode reverseList(ListNode 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 条回复

CV大神普通 2023年6月22日下午4:03

“`java
public ListNode reverseList(ListNode head) {
if (head == null) {
return head;
}
ListNode fakeHead = new ListNode(0);
//假头指向真头
fakeHead.next = head;
//从第二个开始
ListNode current = head.next;
//这一步避免形成环路
head.next = null;
//避免链表丢失，用来保存下一个
ListNode temp;
while (current != null) {
//记录下一个
temp = current.next;
//插入到假头和真头之间
current.next = fakeHead.next;
fakeHead.next = current;
//继续下一个
current = temp;

}
return fakeHead.next;
}

“`java
时间复杂度：O（n），空间复杂度O（1）

0 赞同 0 条回复

&Camille 普通 2023年6月22日下午3:58

class Solution {
public ListNode reverseList(ListNode 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 条回复

彦，，# 普通 2023年6月21日下午11:56

递归算法

 ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        ListNode* reversedList = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return reversedList;
    }

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月21日下午11:16

struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL){
            return head;
    }
    struct ListNode* pre = NULL;
    struct ListNode* cur = NULL;
    while(head != NULL){//反转
        cur = head->next;
        head->next = pre;
        pre = head;
        head = cur;
    }
    return pre;
}

struct ListNode* cur = head;
struct ListNode* pre = NULL;
while(cur != NULL){
    struct ListNode* temp = cur->next;
    cur->next = pre;
    pre = cur;
    cur = temp;
}
return pre;

}

1 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午6:47

struct ListNode* reverseList(struct ListNode* head){
struct ListNode*pre=NULL;//将指向后继节点改为指向前驱节点
struct ListNode*cur=head;
while(cur)
{
   struct ListNode*next=cur->next;//保存剩下未处理的节点
    cur->next=pre;
    pre=cur;//pre指针后移一位
    cur=next;//cur指针后移一位
}
 return pre;
}

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

0 赞同 0 条回复

Dsjh 普通 2023年6月21日下午3:46

“`c++
// c++实现
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next){
return head;
}
ListNode* newhead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return newhead;
}
};

0 赞同 0 条回复

断舍离永久会员 2023年6月21日下午3:40

class Solution {
    public ListNode reverseList(ListNode head) {
        //第一个条件是特殊情况链表为null
        //第二个条件是递归终止条件，当链表为最后一个节点时，及时返回
        if(head == null || head.next == null){
            return head;
        }
        //这里的node在第一次递归出栈会执行return head，此时node就一直是节点5
        ListNode node = reverseList(head.next);
        //从第二次递归出栈时执行以下逻辑（展开两次递归调用逻辑）:
        //第二次递归出栈head为4节点，即4.next.next = 4，此时5→4,4也指向5
        //第三次递归出栈head为3节点，即3.next.next = 3，此时4→3,4也指向3
        head.next.next = head;
        //为了不发生相互指向，将本次递归的head.next指向断掉，即4此时不再指向5
        //为了不发生相互指向，将本次递归的head.next指向断掉，即3此时不再指向4
        head.next = null;
        //返回反转链表后的头节点
        return node;
    }
}

0 赞同 0 条回复

普通 2023年6月21日下午2:52

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next == null){
            return head;
        }
        List list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        ListNode top = list.get(list.size()-1);
        for(int i=list.size()-2;i>=0;i--){
            ListNode right = list.get(i);
            ListNode left = null;
            if(i-1>=0){
                left = list.get(i-1);
            }
            if(i==(list.size()-2)){
                top.next = right;
            }
            right.next = left;
        }
        return top;
    }
}

使用的压栈出栈思路，要是递归、迭代的话好像更好一些

0 赞同 0 条回复

小吕普通 2023年6月21日下午2:14

cpp双指针实现
ListNode* pre = NULL;
ListNode* cur = head;
if(curNULL||(cur!=NULL&&cur->nextNULL))
{
return cur;
}
while(cur!=NULL)
{
ListNode* temp = cur;
cur = cur->next;
temp->next = pre;
pre=temp;
}
return pre;

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午12:27

“`c++
class Solution {
public:
//递归法
ListNode* reverse(ListNode* pre, ListNode*cur){
if(cur == NULL) return pre;//结束条件
ListNode* temp = cur -> next;
cur -> next = pre;

    return reverse(cur, temp);
}


ListNode* reverseList(ListNode* head) {
    return reverse(NULL, head);
}

};
class Solution {
public:
//双指针法
ListNode* reverseList(ListNode* head) {
if(head NULL) return head;
if(head -> next NULL) return head;

    ListNode * cur = head -> next;
    ListNode * pre = head;
    pre -> next = NULL;


    while( cur != NULL){
        ListNode * temp = cur -> next;
        cur -> next = pre;
        pre = cur;
        cur = temp;
    }

    return pre;


}

};

“`

0 赞同 0 条回复

跋扈疙瘩汤普通 2023年6月21日上午11:05

// 用栈解决
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<ListNode*> st;
        ListNode* pre = head; 
        if (!head || !head->next) return head;
        while (pre) {
            st.push(pre);
            pre = pre->next;
        }

        ListNode* cur = st.top();
        pre = cur;
        st.pop();
        while (!st.empty()) {
            ListNode* temp = st.top(); 
            cur->next = temp;
            cur = cur->next;
            st.pop();
        }
        cur->next = nullptr;
        return pre;
    }
};

0 赞同 0 条回复

Bello~ 普通 2023年6月21日上午11:05

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

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

0 赞同 0 条回复

悠若普通 2023年6月21日上午11:01

递归

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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年6月21日上午10:41

原地反转

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode temp=head;
        ListNode pre=null;
        ListNode t;
        while(temp!=null){
            t=temp.next;
            temp.next=pre;
            pre=temp;
            temp=t;
        }
        return pre;
    }
}

0 赞同 0 条回复

局外人普通 2023年6月21日上午9:15

思想：递归

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年6月21日上午8:03

三指针
时间：O(n)
空间：O(1)

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

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月21日上午7:34

# 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 not head or not head.next:
            return head

        prev = None
        cur = head

        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        return prev

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日上午6:45

C++
方法1: for循环遍历反转
TC: O(n)
SC: O(1)

“`C++
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr) {
ListNode *temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
};

方法二: 递归翻转
TC: O(n)
SC: O(n)

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

0 赞同 0 条回复

　　　　　　　　普通 2023年6月21日上午3:05

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

【时间O(n),空间O(1)】
遍历并反转每个指针

0 赞同 0 条回复

残月冷骄阳普通 2023年6月21日上午12:56

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {

//迭代法
ListNode cur = head;
ListNode pre = null;
while(cur!=null){
ListNode tempNode = cur.next;
cur.next = pre;
pre = cur;
cur = tempNode;
}

    return pre;

}

}
““

0 赞同 0 条回复

大鑫啊普通 2023年6月21日上午12:12

时间复杂度：O(n)
空间复杂度：O(n)
1、先总结出递归出口
2、再将当前头结点next结点进行递归
3、想象递归返回时此时指向的head节点，将head.next.next = head (比如链表1234，将3next指向的4的next指向3，将3的next 指向null)

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

0 赞同 0 条回复

Jerry 普通 2023年6月20日下午11:42

public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
    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;
    }
}

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

0 赞同 0 条回复

阿白普通 2023年6月20日下午11:05

思路：递归
时间复杂度O(n）空间复杂度O(n)

/**
 * 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 last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;


    }
}

0 赞同 0 条回复

怀瑾永久会员 2023年6月20日下午10:49

执行用时：0 ms
内存消耗：8.2 MB
思路：
想法：设置两个辅助节点（NULL和头节点），将头节点的下一个节点取出赋给局部节点，然后将NULL赋给头节点的下一个节点，接下来，将改变后的头节点和局部节点作为函数新的变量值继续递归，达到将头节点的下一个节点的值备份后，将被改变的头节点的下一个值作为头节点下一个节点的值，递归结束条件是遍历结束，此时头节点为空。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(NULL, head);
    }
    ListNode* reverse(ListNode* pre, ListNode* temp){
        if(temp == NULL) return pre;
        ListNode* n = temp->next;
        temp->next = pre;
        return reverse(temp, n);
    }
};

0 赞同 0 条回复

硬核洋葱普通 2023年6月20日下午10:40

/**
 * 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)  return NULL;
        ListNode* node = head->next, *prev = head;
        prev->next = NULL;
        while(node){
            ListNode* temp = node->next;
            node->next = prev;
            prev = node;
            node = temp;
        }
        return prev;
    }
};

时间复杂度 O(n)，空间复杂度 O(1)
这个题直接遍历就可以了，只是注意在修改某个节点的next节点时，要保存原来的那个next以方便遍历
而且对第一个节点，它的next字段应当为NULL

0 赞同 0 条回复

江畅普通 2023年6月20日下午10:22

class Solution {
public:
    // 方法一：递归
    // 时间复杂度 O(N)
    // 空间复杂度 O(N)
    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;
    }
};

class Solution {
public:
    // 方法二：原地反转
    // 时间复杂度 O(N)
    // 空间复杂度 O(1)
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;

        while (cur != nullptr) {
            ListNode* next = cur->next;  
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

0 赞同 0 条回复

拾陆. 普通 2023年6月20日下午10:07

/**
 * 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) return nullptr;
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            ListNode* node = cur->next;
            cur->next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
};

可以

0 赞同 0 条回复

yxy 普通 2023年6月20日下午9:55

简单

/**
 * 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* cur = head;
        ListNode* prev = nullptr;
        ListNode* next;
        while(cur)
        {
            next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};

0 赞同 0 条回复

哈哈哈普通 2023年6月20日下午9:55

思路：使用递归的方法，追寻到链表的最终节点，然后以最终节点为头结点重新进行指针定向（说实话，现在头是晕的，递归这当面我是真的不太理解，虽然勉强能写出来，但是估计明天就懵逼了。遇事不决，先行跳过）
时间复杂度为O（n），空间复杂度为O(1)

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

0 赞同 0 条回复

张开怀普通 2023年6月20日下午9:46

class Solution{
public:
     ListNode* reverseList(ListNode* head){
          if(head == nullptr || head->next == nullptr){
               return head;
          }
          // 反转子链表
          ListNode* temp = reverseList(head->next);
          head->next->next = head;
          head->next = nullptr;

          return temp;
     }
}

递归法 =》时间复杂度：O(n)，空间复杂度：O(n)

0 赞同 0 条回复

désire. 普通 2023年6月20日下午9:42

C++原地反转：class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head NULL) return head;
ListNode* cur = head;
ListNode* tmp;
ListNode* pre = NULL;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};

0 赞同 0 条回复

～普通 2023年6月20日下午9:34

递归解法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//base case
if(headnullptr||head->nextnullptr){
return head;
}
ListNode* last = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return last;
}
};
栈解法
class Solution {
public:
ListNode* reverseList(ListNode* head) {

    if(head==nullptr||head->next==nullptr){
        return head;
    }
    stack<ListNode*> stack;
    ListNode* cur = head;
    while(cur){
        stack.push(cur);
        cur = cur->next;
    }
    ListNode* newhead = stack.top();
    stack.pop();
    cur = newhead;
    while(!stack.empty()){
        cur->next = stack.top();
        stack.pop();
        cur = cur->next;
    }
    cur->next = nullptr;
    return newhead;
}

};

0 赞同 0 条回复

* 普通 2023年6月20日下午9:26

c实现
struct ListNode* reverseList(struct ListNode* head){
if(headNULL||head->nextNULL){
return head;
}
struct ListNode* newhead=NULL;
struct ListNode* head_cur=head;
struct ListNode* head_next=head;
while(head_cur){
head_next=head_cur->next;
head_cur->next=newhead;
newhead=head_cur;
head_cur=head_next;
}
return newhead;
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月20日下午9:10

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

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;
        ListNode prev = null;
        ListNode after = null;
        while(head != null) {
            after = head.next;
            head.next = prev;
            prev = head;
            head = after;
        }

        return prev;
    }
}

递归反转
解法没想出来，被自己绕晕

0 赞同 0 条回复

jhfuture 普通 2023年6月20日下午9:00

使用java实现

   public ListNode reverseList(ListNode head) {
        // 一、原地反转
        // if(head==null || head.next==null) return head; 
        // ListNode curl=head;
        // ListNode pre=null;
        // ListNode tmp=head.next;
        // while(curl!=null){
        //     tmp=curl.next;
        //     curl.next=pre;
        //     pre=curl;
        //     curl=tmp;
        // }
        // return pre;
        //二、递归
        //2.1对子链表进行反转
        if(head==null || head.next==null) return head; 
        ListNode tmp=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return tmp;
    }

原地的时间复杂度为n，空间为1，反转时间复杂为n，空间为n
思路：如果是原地的话主要运用了两个指针较为简单，而反转递归的思想，则和视频中介绍的有一些不同，是从最后一个开始 head.next=null，是为了避免闭环！

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午8:44

思路：单向链表只能指向后面不能指向前面所以主要想法是定义一个新的指针记录当前节点的前驱节点，令当前节点指向其前驱节点，实现翻转。
···c++
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 找到前驱节点
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur){
ListNode* temp = cur->next;
cur->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月20日下午8:24

//递归实现,时间O(n)，空间O(n)
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;
}

//原地反转,时间O(n)，空间O(1)
public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }

    ListNode cur = head;
    ListNode newHead = null;

    while(cur != null){
        //先保住子链表
        ListNode subList = cur.next;

        //反转自己
        cur.next = newHead;
        newHead = cur;

        //处理子链表
        cur = subList;
    }

    return newHead;
}

0 赞同 0 条回复

Vow the vow。普通 2023年6月20日下午8:10

递归比较难理解，主要就是要想好返回值和当前节点的操作。

// 法一：递归
    // public ListNode reverseList(ListNode head) {
    //     return reverse(head);
    // }

    private ListNode reverse(ListNode node){
        if(node == null || node.next == null) return node;
        ListNode newHead = reverse(node.next);
        ListNode next = node.next;
        node.next.next = node;
        node.next = null;
        return newHead;
    }

    // 法二：迭代
     public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head != null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
     }

0 赞同 0 条回复

伏月三十普通 2023年6月20日下午8:01

1.原地反转参考帅地
class Solution {
public ListNode reverseList(ListNode head) {
if(headnull || head.nextnull){
return head;
}
ListNode cur=head;
ListNode pre=null;

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

    //cur为空的时候就跳出循环了
    return pre;

}

}

2.递归实现
class Solution {
public ListNode reverseList(ListNode head) {
if(headnull || head.nextnull){
return head;
}

    ListNode last=reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return last;
}

}

0 赞同 0 条回复

行动派小彩笔普通 2023年6月20日下午7:47

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 /*
// 遍历的方式，用pre记录前节点，cur表示当前遍历节点，每个将cur的next指向pre
// 最后pre 指向 反转链表的头节点，cur指向空，时间复杂度O(n)，空间复杂度O(1)


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      if(head==NULL||head->next==NULL) return head;
      ListNode* pre = NULL,*cur = head; 
      while(cur!=NULL)
      {
          ListNode* tmp = cur->next;
          cur->next = pre;
          pre = cur;
          cur = tmp;
      }
      return pre;

    }
    ;
};
*/
// 递归解法，时间O(n)，空间O(n)-递归深度
// 假定reverseList(head->next);已经是逆序的了，那需要把head->next的next指向head再把head置NULL
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
      if(head==NULL||head->next==NULL) return head;
      ListNode* tmp = reverseList(head->next);
      head->next->next = head;
      head->next = NULL;
      return tmp;
    }
    ;
};

0 赞同 0 条回复

peach 普通 2023年6月20日下午7:24

思路

可以使用递归和原地反转两种逻辑

代码

 //递归解法
 //时间复杂度O(n) 空间复杂度O(n)
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head; //递归终止条件，因为有head.next.next，因此这里需要判断
        //1 -> 2 -> 3 head为1
        ListNode temp = reverseList(head.next);//这步保证的是 1 -> 2 <- 3 返回的为3
        head.next.next = head;// 1 <-> 2 <- 3
        head.next = null;// 1 <- 2 <- 3
        return temp;//最后返回3
    }
}
 //原地反转
//时间复杂度O(n) 空间复杂度O(1)
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = head;
        ListNode c = head.next;
        ListNode t;
        while(c != null){
            t = c.next;
            c.next = p;
            if(p == head) p.next = null;//p为头节点的时候，把它设置为尾节点
            p = c;
            c = t;
        }
        return p;
    }
}

0 赞同 0 条回复

Ming 普通 2023年6月20日下午7:04

这里是Ming的打卡：
思路1：递归
//演示temp第一次被赋值时情况：
//temp = 5 temp.next = null;
//此时参数head为4; head.next.next = head 也就是 5.next = 4; head.next = null 主要用于temp最后一次赋值时

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //利用递归实现反转
        //演示temp第一次被赋值时情况：
        //temp = 5 temp.next = null;  
        //此时参数head为4; head.next.next = head 也就是 5.next = 4; head.next = null 主要用于temp最后一次赋值时

        //终止条件，让head停在最后一个结点
        if(head == null || head.next == null) {
            return head;
        }
        ListNode temp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return temp;
    }
}

思路2：原地反转：双指针，前驱指向null，后面指向现结点，cur.next = pre达到效果

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //利用双指针，前驱指向null，后面指向现结点，cur.next = pre达到效果
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //返回调转过来的链表，头结点是pre
        return pre;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午6:21

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr;
        ListNode *cur=head;
        while(cur!=nullptr)
        {
            ListNode *temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};

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

0 赞同 0 条回复

雨落圆荷普通 2023年6月20日下午5:00

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

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

0 赞同 0 条回复

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

共以下 75 个回答

方法一：原地反转（迭代）+ 双指针

方法二：递归

思路

代码

# 回答此问题取消回复

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

共以下 75 个回答

方法一：原地反转（迭代）+ 双指针

方法二：递归

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复