Nancy - 206. Reverse Linked List [Easy] [Linked List]

题意

Reverse a singly linked list.
反转一个单链表。

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

思路一

直接在原链表操作，通过迭代将节点重组，前面的节点转移到重组链表的后面。实际上就是头结点倒插操作。

# 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    # | data | next --|--> new_head  (p.next 的指针指向 new_head)
            new_head = p
        return new_head

思路二

利用栈结构，将链表内容依次压入栈，再从栈依次弹出即可构造逆序。下面的代码用普通数组模拟栈。

# 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

LeetCode 206. Reverse Linked List
206. Reverse Linked List [easy] (Python)
python数据结构之链表（一）
python 数据结构之单链表的实现

您现在的位置是：网站首页>>LeetCode

206. Reverse Linked List [Easy] [Linked List]

题意

思路一

思路二