单链表反转这道题可谓是链表里面的高频问题了,差不多可以说只要被问到链表,就会问单链表反转。 今天我们就一起来看下。
题目链接:https://leetcode-cn.com/problems/reverse-linked-list/
点击文末的阅读原文也可到达。
题目描述:
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
这道题是非常经典的一道题了,没有很多的套路,主要方法有迭代法和递归法两种方法实现。
个人感觉做链表题目,最重要的还是自己多写,多练。
迭代法就是相当于假设有两个链表,其中一个链表是空的,我们要做的工作就是把当前链表的元素不断移动到空链表上。
Python3 实现
# 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: ListNode) -> ListNode:
if head is None or head.next is None:
return head
# pre 就是那个空链表
pre, cur = None, head
# 不断将当前链表移动到空链表上
while cur:
next_node = cur.next
cur.next = pre
pre = cur
cur = next_node
return pre
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 pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
时间复杂度:
空间复杂度:
Python3 实现
# 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: ListNode) -> ListNode:
if head is None or head.next is None:
return head
node = self.reverseList(head.next)
head.next.next = head
# 防止出现环
head.next = None
return node
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 node = this.reverseList(head.next);
head.next.next = head;
head.next = null;
return node;
}
}
时间复杂度:
空间复杂度:
递归法的时间复杂度比迭代法的空间复杂度要高,虽然时间复杂度是一样的,但是递归调用需要额外的时间开销,所以第一种方法是首选,但是如果被问到有没有其他的方法,如果能够说出第二种方法,那就能够起到锦上添花的效果了。
关于链表的基础知识,可以观看下面的动画: