剑指Offer24-反转链表

兴趣爱好交流 每日一题
1

剑指Offer24-反转链表

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

示例:


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

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

限制：


0 <= 节点个数 <= 5000

来源：力扣（LeetCode）

链接：力扣

一解

每次迭代保存“前节点”，并且使“当前节点”指向“前节点”：

961×301 6.02 KB 


# 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:

        cur = head

        pre = None

        while cur:

            next = cur.next

            cur.next = pre

            pre = cur

            cur = next

            

        return pre
2 
class Solution:

    def reverseList(self, head: ListNode) -> ListNode:
          if head ==None or head.next == None:
               return head
          node = self.reverseList(head.next)
          head.next.next = head
          head.next=None
          return node
3

递归可以解，但空间复杂度高，可以尝试优化下

4 
class ListNode:

    def __init__(self, x, next_node=None):
        self.val = x
        self.next = next_node

    @property
    def value(self):
        result = []
        node = self
        while node:
            result.append(node.val)
            node = node.next
        return result


class Solution3:
    def reverseList(self, head):
        if head is None:
            return None
        cur = head
        while head.next:
            t = head.next.next
            head.next.next = cur
            cur = head.next
            head.next = t
        return cur


a = ListNode("a", ListNode("b", ListNode("c")))
b = ListNode("b")
c = None

assert Solution3().reverseList(a).value == ["c", "b", "a"]
assert Solution3().reverseList(b).value == ["b"]
assert Solution3().reverseList(c) is None