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

mpweixin用户普通 2023年8月2日下午1:09

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

双指针同步移动，相差一位，据此修改链表结点指向
时间复杂度：O(N)
空间复杂度：O(1)

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月20日下午11:07

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)

0 赞同 0 条回复

始料未及普通 2023年7月19日下午10:43

两种解法：
1、双指针pre 在前，cur在后，不断改变指针方向
2、递归每次递归的参数也是 pre 和 cur，curnull，开始返回，返回的是最后节点中间递归不改变这个节点只当作结果返回。
注意每次回归到上一层，指向的cur 和 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) {
// return recur(null,head);

// }
// public ListNode recur(ListNode pre,ListNode cur){
// if(curnull){
// return pre;
// }
// ListNode newHead =recur(cur,cur.next);
// cur.next=pre;
// return newHead;
// }
// }

class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
ListNode temp=null;

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

}

}

0 赞同 0 条回复

今天没时间刷题普通 2023年7月19日上午1:09

//递归，空间On，时间On
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;
    }
};

//原地  空间O1，时间On
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
        {
            return head;
        }
        ListNode* pre = nullptr;
        ListNode* curr = head;
        while(curr)
        {
            ListNode* temp = curr->next;
            curr->next = pre;
            pre = curr;
            curr = temp;
        }
        return pre;
    }
};

0 赞同 0 条回复

hi 普通 2023年7月16日下午5:49

/**
 * 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 || !head -> next) return head;
        ListNode* a = head;
        ListNode* b = head -> next;
        ListNode* c;

        while(b)
        {
            c = b -> next;
            b -> next = a;
            a = b, b = c;
        }
        head -> next = NULL;
        return a; 
    }
};
//2. 递归方法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head -> next) return head;

        ListNode* tail = reverseList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;

        return tail; 
    }
};

0 赞同 0 条回复

新禾普通 2023年7月16日下午3:51

// 迭代法，时间复杂度o1，空间复杂度on
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;
}

}

// 时间复杂度on 空间复杂度on 递归深度达到 on
public ListNode reverseList(ListNode head) {
return reverse(head, null);
}
private ListNode reverse(ListNode cur, ListNode pre) {
if (cur null) return pre;
ListNode res = reverse(cur.next, cur);
cur.next = pre;
return res;
}

0 赞同 0 条回复

wowo 普通 2023年7月14日上午9:03

递归
时间复杂度O(n)，空间复杂度O(n)

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

        newhead = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return newhead

迭代（原地反转）
时间复杂度O(n)，空间复杂度O(1)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head

        while curr:
            next_curr = curr.next
            next_prev = curr # don't use prev.next

            curr.next = prev

            curr = next_curr
            prev = next_prev

        return prev

0 赞同 0 条回复

Edenms-u 普通 2023年7月13日下午11:23

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverse(struct ListNode* head, struct ListNode* nhead){
    if(!nhead->next){
        nhead->next = head;
        return nhead;
    }else{
        struct ListNode* temp = reverse(nhead, nhead->next);
    nhead->next = head;
    return temp;
    }
}

struct ListNode* reverseList(struct ListNode* head){
    if(!head)
        return head;
    
    struct ListNode* nhead=head->next, *tail = head, *temp;
    /*
    while(nhead != NULL){
        temp = nhead;
        nhead = nhead->next;
        temp->next = head;
        head=temp;
    }
    tail->next = NULL;
    return head;
    */
    temp = reverse(head, head);
    head->next = NULL;
    
    return temp;
}

原地反转+递归

0 赞同 0 条回复

望仔普通 2023年7月12日下午8:26

func reverseList(head *ListNode) *ListNode {
    return rever(head, nil)
}

func rever(cur, pre *ListNode) *ListNode {
    /*
        递归反转，到尾部时退出
        否则，继续反转其他节点
        修改节点引用指向
        返回反转链表的头节点
    */

    if cur == nil {
        return pre
    }

    res := rever(cur.Next, cur)
    cur.Next = pre
    return res
}

0 赞同 0 条回复

momo 普通 2023年7月12日上午10:09

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

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

0 赞同 0 条回复

Rico 普通 2023年7月11日下午7:39

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode <em>cur = head, *pre = nullptr;
        while(cur != nullptr) {
            ListNode</em> tmp = cur->next; // 暂存后继节点 cur.next
            cur->next = pre;           // 修改 next 引用指向
            pre = cur;                 // pre 暂存 cur
            cur = tmp;                 // cur 访问下一节点
        }
        return pre;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月11日下午5:21

//打卡
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head){
            return nullptr;
        }
        ListNode *p,*q,*r;
        p = nullptr;
        q = head;
        r = head->next;
        while(r){
            q->next = p;
            p = q;
            q = r;
            r = r->next;
        }
        q->next = p;
        return q;
    }
};

0 赞同 0 条回复

达浪达浪普通 2023年7月11日下午12:19

递归法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode* new_listnode=reverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return new_listnode;
    }
};

0 赞同 0 条回复

w 普通 2023年7月11日上午11:26

用了迭代的方法

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月11日上午10:56

public ListNode reverseList(ListNode head) {
//原地肯定用插头法
ListNode pre =new ListNode();
ListNode temp ;
pre.next=null;
while(head!=null)
{
temp=head;
head=head.next;
temp.next=pre.next;
pre.next=temp;

            }
            return pre.next;
}

0 赞同 0 条回复

周小二普通 2023年7月10日下午10:05

代码：

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

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

0 赞同 0 条回复

offer收割机普通 2023年7月10日下午1:58

双指针

考虑遍历链表，并在访问各节点时修改 next 引用指向

时间复杂度

O（n）：遍历链表使用时间

空间复杂度

O（1）：变量pre 和 cur 使用常数大小的额外空间

 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年7月10日上午11:46

原地调转。

/**
 * 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,*cur,*next,*tmp;
        pre=NULL;
        cur=head;
        if(cur == NULL || cur->next == NULL)return head;
        next=cur->next;

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

            pre=cur;
            cur=next;
            next=tmp;

        }
        return cur;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日上午11:46

原地调转。

/**
 * 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,*cur,*next,*tmp;
        pre=NULL;
        cur=head;
        if(cur == NULL || cur->next == NULL)return head;
        next=cur->next;

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

            pre=cur;
            cur=next;
            next=tmp;

        }
        return cur;
    }
};

0 赞同 0 条回复

V2ero 普通 2023年7月10日上午10:54

/*
原地反转
*/
function reverseList(head: ListNode | null): ListNode | null {
    let pre = null;
    let cur = head;
    while(cur){
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next
    }

    return pre
};
/*
递归反转
*/
function reverseList(head: ListNode | null): ListNode | null {
    // 递归边界
    if (!head || !head.next) {
        return head;
    }
    const newHead = reverseList(head.next);
    head.next.next = head; // 最后一次递归节点为倒数第二个
    head.next = null; // 避免成环
    return newHead;
}

0 赞同 0 条回复

Evilluu 普通 2023年7月10日上午10:04

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
#dumpy=ListNode(None)
dumpy = None
if head None:
return None
pre = dumpy
cur = head
while cur:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
双指针

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午11: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;
        }


<pre><code>    ListNode last = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return last;
}
</code></pre>

}
递归

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午10:49

public ListNode reverseList(ListNode head) {
if(headnull || head.next null)return head;
ListNode temp = reverseList(head.next);
head.next.next=head;
head.next=null;
return temp;
}
时间复杂度、空间复杂度都为O（n）

0 赞同 0 条回复

ㅤ 普通 2023年7月9日下午10:22

/**
     * 剑指 Offer 24. 反转链表
     * https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/
     * 思路：使用头插法
     */
    public ListNode reverseList(ListNode head) {
        ListNode root = null, temp = null;
        // 使用头插法将值插入新链表中
        while (head != null) {
            // 省去创建节点一步，将head当前这个节点作为新的节点
            temp = head.next;
            head.next = root;
            root = head;
            head = temp;
        }
        return root;
    }

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午9:49

打卡：
class linkelist:

def __init__(self, data=None):
    self.data = data
    self.head = None
    self.next = None

def recurse_reverse(self, head):
    def recur(cur, pre):
        if not cur:
            return pre
        else:
            lis = recur(cur.next, cur)
            cur.next = pre
            return lis

    return recur(head, None)

0 赞同 0 条回复

爱吃胡萝卜🥕的兔子🐰 普通 2023年7月9日下午9:37

打卡

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head

    for cur != nil{
        behind := cur.Next
        cur.Next = pre
        pre = cur
        cur = behind    
    }

    return pre
}

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月9日下午9:07

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
// C++实现，反转链表
class Solution {
public:
ListNode reverseList(ListNode* head) {
if (head nullptr || head->next nullptr) {
return head;
}
ListNode* reverseListHead = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return reverseListHead;

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

0 赞同 0 条回复

KCOcean 普通 2023年7月9日下午6:57

代码

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

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

0 赞同 0 条回复

神经蛙普通 2023年7月9日下午6:54

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

class Solution {

    public ListNode reverseList(ListNode head) {
        return reverse(head, null);
    }

    private ListNode reverse(ListNode cur, ListNode pre) {
        // 递归结束条件
        if (cur == null) {
            return pre;
        }
        // 获得处理后的节点
        ListNode res = reverse(cur.next, cur);
        // 将当前节点的next指向null
        cur.next = pre;
        return res;
    }
}

0 赞同 0 条回复

艺普通 2023年7月9日下午6:14

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

“`c++
/**
* 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,*pre,*nex;
cur=head;
pre=NULL;
while(cur)
{
nex=cur->next;
cur->next=pre;
pre=cur;
cur=nex;
}
return pre;
}
};
“`

0 赞同 0 条回复

Mooby 普通 2023年7月9日下午6:00

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

0 赞同 0 条回复

CKX 普通 2023年7月9日下午4:55

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head
    for curr != nil {
        temp := curr.Next
        curr.Next = prev
        prev = curr
        curr = temp
    }
    return prev
}
- 时间O(n)
- 空间O(1)

0 赞同 0 条回复

片言莫语普通 2023年7月9日下午4:09

class Solution {
    public ListNode reverseList(ListNode head) {
 /*       // 方法一 递归 时间复杂度 O(n) 空间复杂度O(n)，因为递归调用消耗了n层栈
        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)
        if(head == null || head.next == null){  //特殊情况判断
            return head;
        }
        ListNode pre = null,cur = head;
        while(cur != null){
            ListNode temp = cur.next;   //cur后面的值存起来
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;

    }

}

0 赞同 0 条回复

3A87 普通 2023年7月9日下午3:46

/**
 * 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||head->next==nullptr) return head;

        //反转以temp为头节点的子链表
        ListNode* temp=reverseList(head->next);
        //递归公式
        //1后面2的后面是？1
        head->next->next=head;
        //1的后面是？0
        head->next=nullptr;

        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==nullptr||head->next==nullptr) return head;


        ListNode* pre=nullptr;
        ListNode* cur=head;

        while(cur!=nullptr)
        {
            ListNode* temp=cur->next; //提前保存下
            cur->next=pre; //原地反转
            //移动一位
            pre=cur; 
            cur=temp;
        }

        return pre;
    }

};

0 赞同 0 条回复

刹那芳间普通 2023年7月9日下午3:45

/**
    递归
 */
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 条回复

ppopp 普通 2023年7月9日下午3:31

/**
 * 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 || head -> next == nullptr)  return head;//如果链表为空或者链表只有一个节点，返回本身即可
        ListNode* last = reverseList(head -> next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午12:44

时间复杂度：O(n)
空间复杂度：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){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月9日下午12:11

递归写法

找到递归终止条件，也就是反转链表的第一个节点，就是原链表的最后一个节点。
写子递归，本题就是 head.next
最后把剩下的节点拼接上，也就是改变指针指向的操作。

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

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

原地反转

用多个指针维护链表，pre表示往前的指针，cur表示当前元素的指针，tmp则记录了原链表元素中的下一个元素的指针。
原地反转只需要3步: 当前元素的next指向前一个元素; 往前的指针往后移，即到当前元素; 当前元素指针往后移。

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

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

0 赞同 0 条回复

June 普通 2023年7月9日上午9:23

/**
 * 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 fast = head.next;
        ListNode slow = head;

        while(fast!=null)
        {
            //System.out.println(fast.val);
            ListNode tmp = fast.next;
            fast.next = slow;
            slow = fast;
            fast = tmp;
        }
        head.next = null;

        return slow;
    }
}

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

0 赞同 0 条回复

枫梓。普通 2023年7月9日上午9:20

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

原地反转链表， O(n)时间 O(1)空间。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {

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

递归法，双O(n)

0 赞同 0 条回复

人生何处不青山普通 2023年7月8日下午11:45

估计也就我用TS了

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let cur: ListNode | null = head;
    while(cur) {
        let next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
};

0 赞同 0 条回复

朱志刚普通 2023年7月8日下午10:32

“`cpp
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;



}

};
”’递归

“`cpp
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next)return head;

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

    }



    return pre;



}

};
“`
原地翻转

0 赞同 0 条回复

普通 2023年7月8日下午10:21

c++ 原地翻转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(headNULL) return NULL;
ListNode* pre=NULL,* ne=NULL,*cur=head;
while(cur)
{
ne=cur->next;
cur->next=pre;
pre=cur;
cur=ne;
}
return pre;
}
};

0 赞同 0 条回复

#00456B 普通 2023年7月8日下午10:14

方法一

原地反转。使用双指针对前后两个节点进行反转，依次进行。

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

方法二

递归

/**
 * 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* temp = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return temp;
    }
};

0 赞同 0 条回复

醒醒醒醒普通 2023年7月8日下午10:08

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* reverseList(struct ListNode* head){
    if(head == NULL || head->next == NULL){
        return head;
    }

    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL;

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

    return pre;

}

利用迭代循环

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月8日下午9:50

class Solution {
    public ListNode reverseList(ListNode head) {
        // 原地反转，不借助栈空间
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode temp = cur.next;
            // 只用反转pre和next的链接即可
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

北辰普通 2023年7月8日下午9:25

public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) {
            return head;
        }
        ListNode p = head.next,q;
        if(head.next.next==null) {
            head.next = null;
            p.next = head;
            head=p;
        } else {
            q = p.next;
            head.next=null;
            while(p.next!=null) {
                p.next = head;
                head = p;
                p=q;
                q = p.next;
            }
            p.next = head;
            head=p;
        }
        return head;
    }

时间复杂度：O（n)
空间复杂度：O（1）
思路：本题需要分类讨论，考虑当链表长度为2和长度大于2两种情况
当长度大于2是要注意用两个指针时，需要在循环的最后再进行指针的变换

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月8日下午8:18

代码如下

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

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

0 赞同 0 条回复

阿尚普通 2023年7月8日下午8:16

//原地反转
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;

        ListNode pre = null;
        ListNode nxt = null;

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

        return pre;//pre即为反转链表的头节点
    }
}

//递归
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode h = process(null, head);

        return h;
    }

    public ListNode process(ListNode pre, ListNode cur){
        if(cur == null) return pre;//遍历到链表尾部，pre即为反转链表的头节点

        ListNode nxt = cur.next;
        cur.next = pre;

        return process(cur, nxt);
    }
}

1 赞同 0 条回复

桎梏普通 2023年7月8日下午8:12

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

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

0 赞同 0 条回复

CaCO3 永久会员 2023年7月8日下午7:55

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

0 赞同 0 条回复

小季同学普通 2023年7月8日下午7:00

迭代、递归

//法一
function reverseList(head: ListNode | null): ListNode | null {
    // 边界判断
    if(!head || !head.next) return head
    let prev: ListNode | null = null
    let curr: ListNode = head
    while(curr) {
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }
    return prev
};

// 方法二

function reverseList(head: ListNode | null): ListNode | null {
    // 边界判断
    if(!head || !head.next) return head
    const newHead = reverseList(head.next)
    head.next.next = head
    head.next = null
    return newHead
};

0 赞同 0 条回复

旺旺旺普通 2023年7月8日下午6:53

以下是代码

# 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
        """
        pre=None
        cur =head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre

0 赞同 0 条回复

H、普通 2023年7月8日下午6:37

迭代

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


}

0 赞同 0 条回复

Luminous 普通 2023年7月8日下午5:14

头插法反转：

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

时间复杂度：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 recur(ListNode p){
        if(p==null||p.next==null){
            return p;
        }
        ListNode tmp=recur(p.next);
        p.next.next=p;
        p.next=null;
        return tmp;
    }
    public ListNode reverseList(ListNode head) {
        //使用递归法
        return recur(head);
    }
}

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

0 赞同 0 条回复

一琬人间烟火普通 2023年7月8日下午4:59

固定步骤，直接理解记住就行C++
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pt=head;
ListNode* n=NULL;
ListNode* tp;
while(pt){
tp=pt->next;
pt->next=n;
n=pt;
pt=tp;
}
return n;

};

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午3:55

class Solution {
    public ListNode reverseList(ListNode head) {
        // 输入: 1->2->3->4->5->NULL
        //输出: 5->4->3->2->1->NULL
        ListNode cur = head;
        ListNode pre = null, next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

从第一个开始反转，一个一个来，不要着急，条理清晰。

0 赞同 0 条回复

ONE PIECE 普通 2023年7月8日下午3:29

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

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

0 赞同 0 条回复

Terence💧 普通 2023年7月8日下午2:54

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre, cur *ListNode = nil, head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

时间复杂度：O(n)

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月8日下午2:21

Day2：下面是代码
#双指针

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年7月8日下午2:15

迭代

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

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

时间复杂度：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* reverseTwoNodes(ListNode* cur, ListNode* prev){
        if(cur == nullptr){
            return prev;
        }
        ListNode* res = reverseTwoNodes(cur->next, cur);
        cur->next = prev;
        return res;
    }
    ListNode* reverseList(ListNode* head) {
        return reverseTwoNodes(head, nullptr);
    }
};

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

0 赞同 0 条回复

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

共以下 61 个回答

双指针

时间复杂度

空间复杂度

递归写法

原地反转

方法一

方法二

# 回答此问题取消回复

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

共以下 61 个回答

双指针

时间复杂度

空间复杂度

递归写法

原地反转

方法一

方法二

# 回答此问题 取消回复

# 回答此问题取消回复