Today we are going to do a topic in LeetCode, the original topic link: reference Offer 24. Reverse a linked list

Topic describes

  • Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.
  • Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code
  • Limitations:
0 <= Number of nodes <= 5000Copy the code

Thought analysis

  • Regenerate a new linked list using an external array in reverse order
  • Double pointer traversal
  • The recursive method
    • The termination condition is either the current node or the next node ==None
    • Inside the function, change the direction of the node, that is, the next node of the head points to the head recursive functionhead.next.next = headNext is 5, head. Next is None, head. Next is None, and None is returned recurrently

code

# Python # Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ # # 1. # r_list = [] # while head: # r_list.append(head.val) # head = head.next # r_head = cur = ListNode(0) # for r in r_list[::-1]: # cur.next = ListNode(r) # cur = cur.next # return r_head.next # # 2. # r_head = None # while head: # tmp = head.next # head.next = r_head # r_head = head # head = tmp # return r_head # 3. If not head or not head. Next: return head cur = self.reverseList(head.next) head.next.next = head head.next = None return curCopy the code

conclusion

  • Using external queues is the simplest and most straightforward, with the worst performance
  • Double pointer always
  • Iterative methods have the best performance, but the logic is the hardest

The appendix

  • Leetcode-cn.com/problems/fa…

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign