题目地址(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 为数组长度。
- 时间复杂度:
- 空间复杂度:
网友评论