美文网首页
206. 反转链表

206. 反转链表

作者: 王侦 | 来源:发表于2022-09-26 09:03 被阅读0次

题目地址(206. 反转链表)

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

题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

前置知识

公司

  • 暂无

思路

关键点

  • 链表的基本操作(交换)
  • 虚拟节点dummy简化操作
  • 注意更新next和pre的位置,否则有可能出现溢出

代码

  • 语言支持:Java

Java Code:


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

Go Code

/**
 * 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
    }
    // nil 是 interface、function、pointer、map、slice 和 channel 类型变量的默认初始值。但声明时不指定类型,编译器也无法推断出变量的具体类型。
    var prev, next *ListNode = nil, head
    for next != nil {
        tmp := next.Next
        next.Next = prev
        prev = next
        next = tmp
    }
    return prev
}

复杂度分析

令 n 为数组长度。

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

相关文章

网友评论

      本文标题:206. 反转链表

      本文链接:https://www.haomeiwen.com/subject/tjmtartx.html