剑指 Offer 24. 反转链表

问题描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

 

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

 

限制：

0 <= 节点个数 <= 5000

 

注意：本题与主站 206 题相同：https://leetcode-cn.com/problems/reverse-linked-list/

解题思路

• 迭代

添加一个虚拟头结点，然后使用头插法构建链表。

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        vhead = ListNode(0)
        cur = head
        while cur:
            nxt = cur.next
            cur.next = vhead.next
            vhead.next = cur
            cur = nxt
        return vhead.next

• 递归

1-->2-->3-->4-->5 假设 2-->3-->4-->5 已经反转好了变为了 5-->4-->3-->2。

而 1 最开始是指向 2，所以此时只要设置 2.next = 1 和 1.next = None。

• 即 1.next.next = 1
• 1.next = None

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        rest_head = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return rest_head

返回顶部

在手机上阅读