206. Reverse Linked List 反转链表

最新推荐文章于 2024-12-10 18:40:02 发布

puspos

最新推荐文章于 2024-12-10 18:40:02 发布

阅读量198

点赞数

分类专栏： leetcode 文章标签：链表

本文链接：https://blog.csdn.net/puspos/article/details/120538194

版权

leetcode 专栏收录该内容

235 篇文章

订阅专栏

本文介绍了两种链表翻转的方法，包括使用递归实现的O(N)时间复杂度的解法和非递归的前插法。递归解法通过两次调用自身完成翻转，而前插法通过迭代不断调整节点的指针实现翻转。这两种方法都有效地解决了链表反转的问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

问题

在这里插入图片描述

解法

1. 递归 O(N)

在这里插入图片描述

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


        ListNode nextNode=head.next;
        ListNode newHead=reverseList(nextNode);
        
        head.next=null;
        nextNode.next=head;


        return newHead;

    }
}
class Solution {
	//head没有反转的部分的第一个节点，prev已经反转的链表的第一个节点
	//返回已经反转的部分
    public ListNode reverseList(ListNode head, ListNode prev) {
    	//此时全部节点反转
        if(head==null) return prev;
        //将head节点反转，并将其后面的节点继续反转（同时传入已经反转的部分）
        ListNode next = head.next;
        head.next = prev;
        
        return reverseList(next,head)
    }
}

2. 非递归：前插法 O(N)

在这里插入图片描述

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