当前位置：
  1. 首页
  2. 数据结构与算法
  3. 算法系统课
  4. 正文

LeetCode206. 反转链表🌟🌟🌟🌟🌟简单

算法系统课 免费

问题描述

原文链接：206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

代码实现

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode 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;

    }
}

Python

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head or not head.next:
            return head

        newHead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newHead

C++

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

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

    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

发表回复

后才能评论

评论(7)

  • 我来吃饭啦 永久会员 2024年6月18日 下午9:03

    打卡

    # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
#  递归1
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def recur(cur, per):
            if not cur: return per
            res = recur(cur.next, cur)
            cur.next = per
            return res
        return recur(head, None)

    # 递归2
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        newhead = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return newhead
  • Yuki 永久会员 2024年1月29日 上午10:07

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

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

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

    return pre;
}

    };

  • uu 永久会员 2023年9月20日 上午8:03 
    // 【思路】递归
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public ListNode reverseList(ListNode head) {
        //函数目的：反转栈

        //结束条件
        if(head == null || head.next == null) {
            return head;
        }
        //关系式
        ListNode newHead = reverseList(head.next);

        // 不能用newHead，因为newHead要作为表头返回！！！
        // newHead.next = head;
        // head.next = null;
        // newHead = head;
        // return newHead; 

        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
  • uu 永久会员 2023年9月19日 下午11:01 
    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode ans = new ListNode(0, null);
        if(head == null) return null;
        while(head.next != null) {
            ListNode temp = new ListNode(0, null);
            ans.val = head.val;
            head = head.next;
            temp.next = ans;
            ans = temp;

        }
        ans.val = head.val;
        return ans;

    }
}
  • 阿尚 普通 2023年8月17日 上午11:36 
    //反转链表
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) return null;

        ListNode pre = null;
        ListNode cur = head;
        ListNode nxt = null;

        while(cur != null){
            nxt = cur.next;

            cur.next = pre;
            pre = cur;

            cur = nxt;
        }

        return pre;
    }
}

//递归
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;
    }
}
  • 3_🔥 永久会员 2023年7月9日 下午10:33 
    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; //注意这里返回的是pre，因为当cur指向空的时候循环结束，此时头是pre
    }
}

    普通写法，递归见题解

  • 帅气的冬瓜 普通 2023年6月28日 下午2:30

    打卡

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理