两种方法求解链表高频面试题之单链表反转

与你一起学算法

发布于 2021-03-23 12:14:16

3180

发布于 2021-03-23 12:14:16

文章被收录于专栏：与你一起学算法

单链表反转

单链表反转这道题可谓是链表里面的高频问题了，差不多可以说只要被问到链表，就会问单链表反转。 今天我们就一起来看下。

题目链接：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;
    }
}