206. Reverse Linked List [easy] (Python)

Topic link
https://leetcode.com/problems/reverse-linked-list/
The questions in the original

Reverse a singly linked list.

The title translation
Flip a one-way linked list
Thinking method
This topic is relatively basic, and there are many solutions to it, and there are also many solutions to AC. Here, only part of the ideas are sorted out for reference.
Thinking a
Using the stack structure, the contents of the linked list can be pushed onto the stack in turn, and then ejected from the stack in turn to construct the reverse order. The following code emulates the stack with ordinary arrays.
code

# 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
        """
        p = head
        newList = []
        while p:
            newList.insert(0, p.val)
            p = p.next

        p = head
        for v in newList:
            p.val = v
            p = p.next
        return head

Idea 2
Similar to the idea of a stack, but directly in the original linked list operation, by iterating the node reorganization, the previous node moved to the back of the reorganized list. It’s actually an upside-down operation.
code

# 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
        """
        new_head = None
        while head:
            p = head
            head = head.next
            p.next = new_head
            new_head = p
        return new_head

Thought three
Recursion. Notice the termination condition
code

# 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
        """
        if not head or not head.next:
            return head

        p = head.next
        n = self.reverseList(p)

        head.next = None
        p.next = head
        return n

PS: The novice brush LeetCode, the new handwriting blog, write wrong or write unclear please help point out, thank you!
reprint please indicate the: http://blog.csdn.net/coder_orz/article/details/51306170


Read More: